{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 5 : Algebra\n",
    "**References:**\n",
    "* [Introduction to Symbolic Computation](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/index.html), Lectures \n",
    "[11](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec11.html), [12](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec12.html), [28](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec28.html), [38](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec38.html), [40](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec40.html)\n",
    "* [Group theory and Sage](https://doc.sagemath.org/html/en/thematic_tutorials/group_theory.html)\n",
    "* [Polynomials in Sage](https://doc.sagemath.org/html/en/tutorial/tour_polynomial.html)\n",
    "* [Extensions of rings in Sage](https://doc.sagemath.org/html/en/reference/rings/sage/rings/ring_extension.html)\n",
    "\n",
    "**Summary:**<br>\n",
    "We start the lecture by recalling the useful ``sum`` and ``prod`` functions in Python, as well as more general **iterators** (in particular more fancy **list comprehensions** and tools for products of iterators). In the mathematical part, we begin by discussing (finite) **groups** and how to generate and identify them. Then we discuss **polynomial rings** and how to use them to study **field extensions** or **ideals**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python warmup : sum and prod\n",
    "Two extremely useful constructions are the Python functions ``sum`` and ``prod`` for computing sums and products of elements in a list (or more general iterable). Here is the basic usage:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum([3,-2,6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Combined with list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum([i for i in range(1,101)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can in fact leave off the brackets above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(i for i in range(1,101))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apart from summing integers (or rational numbers, etc), we can in fact sum everything that has a ``+`` operation. In some of these cases, we should specify by hand the \"neutral element\" that ``sum`` should start with, which is given as a second argument (the default is the ``int 0``):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum([[1,2],[3,4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum([[1,2],[3,4]], [])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A more interesting application of this last point:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum([[3*i,3*i+1] for i in range(6)],[])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "The [Euler-Mascheroni constant](https://en.wikipedia.org/wiki/Euler%27s_constant) is defined as the limit\n",
    "$$\n",
    "\\gamma = \\lim_{n \\to \\infty} \\left(- \\log(n) + \\sum_{k=1}^n \\frac{1}{k} \\right) = \\int_1^\\infty \\left(\\frac{1}{\\lfloor x \\rfloor} - \\frac{1}{x} \\right) dx\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(1/floor(x), 1,12, color='red', fill=1/x) + plot(1/x, 1, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute its approximation for $n=1000$ (alternatively: compute its first 4 digits) using the ``sum`` function.\n",
    "*Remark:* If you are done early, try to find out if SageMath has this constant stored somewhere."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "gam_approx = -log(1000) + sum(1/k for k in range(1,1001))\n",
    "n(gam_approx)\n",
    "> 0.577220664893197\n",
    "```\n",
    "Using some math (or looking on wikipedia) we can see that the error of approximation of $\\gamma$ by the formula above behaves like $1/2n$. Thus to get $4$ digits, we should try something like $n=50000$:\n",
    "```\n",
    "gam_approx = -log(50000) + sum(1/k for k in range(1,50001))\n",
    "n(gam_approx)\n",
    "> 0.577225664868200\n",
    "```\n",
    "*After* seeing the result, we can note that our $n$ was sufficiently large: adding or subtracting a number of absolute value at most $1/(2\\cdot 50000) = 0.00001$ does not change the first $4$ digits. We can of course also check with the pre-stored value of the constant:\n",
    "```\n",
    "n(euler_gamma)\n",
    "> 0.577215664901533\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can imagine, the function ``prod`` works much the same:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prod(i for i in range(1,51)) == factorial(50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can again take products of more general things. Here is an example: what do you think is the product of all elements in the symmetric group $S_3$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S3 = list(SymmetricGroup(3))\n",
    "prod(S3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The correct answer is: this depends on the order in which we multiply them! Just for fun, here is the set of all elements we can get like this (we'll see these constructions in more detail below and in the next lecture):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{prod(p) for p in Permutations(S3)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are interested in the question what elements you can get like this, have a look at the following [answer to a question on math.stackexchange](https://math.stackexchange.com/a/1355671/311445) and the paper cited there."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python warmup: more iterators\n",
    "In this short section, we'll see a bunch of very useful constructions of iterators (used in ``for``-loops or the constructions of lists).\n",
    "\n",
    "First is a more general version of *list comprehension* that we have seen before. As a reminder, here is the basic version:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [2,3,5,7]\n",
    "[a^2 for a in L]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More generally, we can have multiple ``for`` in the list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[a*b for a in L for b in L]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the output is the list we would have obtained as follows:\n",
    "```\n",
    "result = []\n",
    "for a in L:\n",
    "    for b in L:\n",
    "        result.append(a*b)\n",
    "```\n",
    "In particular, the order of the ``for``-loops matters.\n",
    "\n",
    "In addition we can have an ``if``-condition at the end of the list comprehension. Elements are only added to the list if this comprehension is satisfied:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[a*b for a in L for b in L if a*b > 20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Create the list of\n",
    "* all integers $a$ between 100 and 200 satisfying $a\\ \\mathrm{mod}\\ 3 = 2,\\ a\\ \\mathrm{mod}\\ 7 = 4$\n",
    "* all entries of $\\{0,1\\}^3 = \\{(0,0,0), (1,0,0), \\ldots, (1,1,1)\\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "[a for a in range(100,201) if a % 3 == 2 and a % 7 == 4]\n",
    "> [116, 137, 158, 179, 200]\n",
    "M = [0,1]\n",
    "[(a,b,c) for a in M for b in M for c in M]\n",
    "> \n",
    "[(0, 0, 0),\n",
    " (0, 0, 1),\n",
    " (0, 1, 0),\n",
    " (0, 1, 1),\n",
    " (1, 0, 0),\n",
    " (1, 0, 1),\n",
    " (1, 1, 0),\n",
    " (1, 1, 1)]\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the exercise above, if we had wanted to compute the list $\\{0,1\\}^{10}$, it would have required to write lots of ``for`` statements by hand. Instead, we can use the function ``itertools.product``, which we need to **import** by hand as follows before using it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function ``product`` takes iterables ``A, B, ...`` and returns a generator that we would obtain from the code\n",
    "```\n",
    "((a,b,..) for a in A for b in B ...)\n",
    "```\n",
    "Here is a first example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = [0,1]\n",
    "list(product(M, ['a', 'b', 'c']))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(product(M, repeat=3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a list ``N`` of lists, the function ``product(*N)`` essentially computes the cartesian product of these lists (hence the name):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = [M, M, ['a', 'b', 'c']]\n",
    "list(product(*N))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Consider the following list $L$ of integers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [17,23,31,32,44,59,61,63]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A variant of the [Subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem) asks: what are the ways of writing the number $150$ as a sum\n",
    "$$\n",
    "a_1 + a_2 + a_3 + a_4 = 150,\\quad (a_1, a_2, a_3, a_4 \\in L)?\n",
    "$$\n",
    "Find all such tuples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "[s for s in product(L, repeat=4) if sum(s)==150]\n",
    ">\n",
    "[(23, 32, 32, 63),\n",
    " (23, 32, 63, 32),\n",
    " (23, 63, 32, 32),\n",
    " (31, 31, 44, 44),\n",
    " (31, 44, 31, 44),\n",
    " (31, 44, 44, 31),\n",
    " (32, 23, 32, 63),\n",
    " (32, 23, 63, 32),\n",
    " (32, 32, 23, 63),\n",
    " (32, 32, 63, 23),\n",
    " (32, 63, 23, 32),\n",
    " (32, 63, 32, 23),\n",
    " (44, 31, 31, 44),\n",
    " (44, 31, 44, 31),\n",
    " (44, 44, 31, 31),\n",
    " (63, 23, 32, 32),\n",
    " (63, 32, 23, 32),\n",
    " (63, 32, 32, 23)]\n",
    "```\n",
    "Note that above the order really matters. If we wanted to only list the ways up to reordering, we could insist that the tuple ``s`` is ordered. For this we can compare the sorted list ``sorted(s)`` with the conversion of ``s`` to a list via ``list(s)``:\n",
    "```\n",
    "[s for s in product(L, repeat=4) if sum(s)==150 and sorted(s)==list(s)]\n",
    "> [(23, 32, 32, 63), (31, 31, 44, 44)]\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Group theory\n",
    "One of the fundamental objects in algebra are [groups](https://en.wikipedia.org/wiki/Group_(mathematics)). These are abstractly defined as a tuple $(G, \\circ)$ of a set $G$ and an operation $\\circ : G \\times G \\to G$ satisfying certain axioms (associativity, existence of neutral and inverse elements).\n",
    "\n",
    "While SageMath can work with some forms of infinite groups (in particular with [*finitely presented groups*](https://doc.sagemath.org/html/en/reference/groups/sage/groups/finitely_presented.html)), we will mostly look at *finite* groups today. These are represented in SageMath as **permutation groups**, i.e. subgroups of some symmetric group \n",
    "$$\n",
    "S_n = \\{\\text{permutations of }\\{1, \\ldots, n\\}\\}\n",
    "$$\n",
    "generated by some elements.\n",
    "\n",
    "The full symmetric group $S_n$ is created as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S6 = SymmetricGroup(6); S6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at a random element of $S_6$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S6.random_element()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that it is represented in [*cycle notation*](https://en.wikipedia.org/wiki/Permutation#Cycle_notation). E.g. the element $(1,4)(2,3,6) \\in S_6$ is the permutation sending\n",
    "$$\n",
    "1 \\mapsto 4,\\ 4 \\mapsto 1,\\ 2 \\mapsto 3,\\ 3 \\mapsto 6,\\ 6 \\mapsto 2,\\ 5 \\mapsto 5.\n",
    "$$\n",
    "If we want to create this particular element, this works as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cycle = ((1,4),(2,3,6))\n",
    "a = S6(cycle); a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, we use the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = S6(\"(1,3) (2,5,4)\"); b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can multiply, invert or raise elements to some power in the groups $S_6$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(a*b)\n",
    "print([a^i for i in range(7)])\n",
    "print(b.inverse())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "¡**Careful**!<br>\n",
    "In SageMath, the convention is that given permutations ``a,b``, the permutation ``a*b`` is the permutation obtained by *first* applying ``a`` and then applying ``b``. This is different from the standard notation $a \\circ b$ standing for first applying $b$ and then $a$. It leads to strange things as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a(b(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "(a*b)(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(b*a)(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I must say that I find this a bit strange, but for many operations (computing inverses, subgroups generated by a subset, etc) this order does not really matter. You should just think of the ``SymmetricGroup(n)`` acting on the set $\\{1, \\ldots, n\\}$ *from the right*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course we can also create more general finite groups, some of which are given by pre-defined functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CyclicPermutationGroup(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DihedralGroup(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = AlternatingGroup(5); A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A.is_subgroup(SymmetricGroup(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The phrase ``as a permutation group`` already indicates that the elements of these groups are specified by certain permutations, indicating that they are naturally seen as subgroups of some $S_n$. We can see this in an example by *iterating* through the group to look at its elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = DihedralGroup(3)\n",
    "for g in H:\n",
    "    print(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In many cases, it's sufficient to just have a look at the generators of the group, which we can obtain as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H.gens()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apart from the specific groups mentioned above, we can also create a group ourselves by generating it inside a symmetric group by a list of permutations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = PermutationGroup([(1,2,3,4,5), ((2,5),(3,4))])"
   ]
  },
  {
   "attachments": {
    "image.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAO0AAAD1CAYAAAC8yHJ5AAAgAElEQVR4nO3df1RUdf4/8OfnS94OrRPFZDJLiSaTGmrjKXEV9YzpUmIU5lRSRz3+SCinFnMqd/ewHWs12UWdCjtoK4Ynd3HDJNw0DBeUFcNfICyIDqmDsDPBzqw0HGbnHmbv9w+aKxQg4My87515Pc7hnAy481R4zft93/f94/8EQRBACJGN/8c6ACFkcKhoCZEZKlpCZIaKlhCZoaIlRGaoaAmRGSpaQmSGilbGampqUFBQAJ7nWUchfvR/NLlCvkaPHg2z2Yzi4mLMnTuXdRziJ9TSylRjYyPMZjMAQKVSMU5D/ImKVoacTieWLVsm/jk8PJxhGuJvVLQy9N5776G0tFT8c1hYGMM0xN/onlZmysrKMHv27B7/j36EwYVaWhlpa2vDkiVLAAALFixgnIawQkUrI5s3b4bZbIZWq8WqVasAADExMYxTEX+jopWJK1euYPPmzeA4Djk5OQgJCQEADBs2jHEy4m9UtDLxwQcfAADeeustjBkzBlarFQAwYcIElrEIA1S0MrB//34YjUYolUq88sorACDOglIqlSyjEQaoaCWuoaEBL7zwAgAgPz8fERERAICrV68C6JoVRYILFa2EOZ1OrFmzBjzPY+PGjdBqteLnGhoaAAAjRoxgFY8wQkUrUW63G2+++SaOHDmCuLg4rF27tsfnPS0tFW3woaKVILfbDYPBgKysLKjVauzbtw+hoaGsYxGJoKKVoJycHBiNRqjVahQXFyMyMrLPr6XFAsGHpjFKjNVqxYMPPgiXy4X6+nqMGTOm16+788474XA4UFlZCY1G4+eUhKXbWAcgPS1btgwOhwM7d+7ss2ABwOFw+DEVkRJqaSXEarVCpVJBo9HgzJkz4qynH7Pb7eLz2cuXL/db3CTw0D2thHAcJ/53XwULoMf2MjRAFXyoaBlyu909/luv1wMAEhMT+/2+5uZmAIBCoaBHPkGI7mkZOnr0KJRKJUpLS1FSUoIvv/wSOp0Ob7/9dr/f19LSAgAYO3Zsvy0yCUxUtAyFhIQgOTkZJpMJABAVFYU//OEPNy3E4cOHAwD+85//+DwjkR7qHjPidruRnZ0Nk8mEuLg4OBwOXL16dUCDSlFRUQAAs9ksrvYhwYOKlhG73Y7CwkKkpaWhsLBQbD0HYtSoUeI85I0bN/oqIpEo6h4zMmLECDgcjh4jxoOxfft2rF27FlOnTvVyMiJ19JyWEJmh7jEhMkNFS4jMUNESIjNUtITIDBUtITJDRUuIzFDREiIzVLSEyAwVLSEyQ0VLiMxQ0RIiM1S0hMgMFS0hMkNFS4jMUNESIjNUtITIDBUtITJDRUuIzNAeUTJRU1ODAwcOoLOzE/fffz+SkpJoo/IgRXtEycD+/fvxwgsv9DgOhOM4ZGdnY/ny5QyTERaoeyxxW7ZsgU6nA8/zyMrKwqFDh7BhwwYAwIoVK1BQUMA4IfE3amklrKGhAWq1GhzHIT8/v8cZP4cPH0ZCQgI4jkNxcTFmzZrFMCnxJ2ppJYrnebzxxhsAgK1bt/7kUK758+cjJycHPM9j4cKFuHLlCouYhAEqWok6evQoCgoKEBsbi+Tk5F6/Zvny5cjIyIDNZkNcXBxqamr8nJKwQEUrQSdPnsTKlSsBAG+++SbCw8P7/Np169Zhw4YNsFgsmDNnDurq6vwVk7AiEMmJjY0VAAgbN24c8Pekp6cLAAS1Wi2YzWYfpiOs0UCUxFy5cgUPPPAANBoNKisrB/x9brcbBoMBRqMR8fHxKCgooFPiAxR1jyXE7XZjyZIlANDnfWxfQkJCsGnTJmi1Whw5cgSvvvpqj5PmSQBh3dSTG3JzcwUAglarFTo7O4d0jZaWFkGtVgsAhMzMTC8nJFJA3WOJuHjxIhITE2EymVBRUYHY2NghX6uqqgrTpk0Dz/PIzMzEunXrvJiUsEbdYwlwu9147bXXYDKZsHLlSjzyyCO3dD2NRoOioiIolUoYDAZs377dS0mJFFBLKwG//vWvsXnzZmi1WhQVFQ35oOkfq6mpwaOPPgqe51FdXY1JkyZ55bqELSpaxpxOJ+644w4AgMlkQnR0tFevv2fPHixbtgxarRbFxcUICQnx6vWJ/1H3mDHP9EOVSuX1ggWAF198EVqtFqWlpTh48KDXr0/8j4qWsd/+9rcAIK7c8TbPoyCga3ZVe3u7T16H+A8VLUNbtmwR5xcvW7bMZ68zffp06HQ6mEwmn705ED9i+bwpWHV2dgrr168XAAgcxwlnzpzx+Ws2NTUJSqVSACCkp6cP+TkwYY+KloHMzEwBgKBSqfxSsB4VFRVi4aalpVHhyhQVrZ9lZGQIAASFQiHU19f7/fVNJpNYuCkpKUJHR4ffM5BbQ0XrR1lZWQIAQalUCtXV1cxy1NbWilMd169fzywHGRp6TusnO3bsQGpqKjiOQ0VFBTQaDdM8jY2N+MUvfgGLxYK8vDw8//zzTPOQgaOi9YMtW7bAYDBAoVCgsLAQWq2WdSQAQFlZGWbPng2O41BbW+uT58TE++iRj495ClapVOLEiROSKVgAmDVrFoxGI3iex5o1a1jHIQPFtnce2Pbu3SuJe9j+uFwucaeM3Nxc1nHIAFD32EcuXryIyZMnA4Ak7mH7c/bsWcyYMQOA9LMS6h77BM/zWLlypbjBuNSL4JFHHkF2djZ4nsdzzz0Hu93OOhLpBxWtD2RmZuLEiRNISkrCihUrWMcZkOXLlyMlJUVc0+t0OllHIn1h3T8PNDk5OeJ9rNx2Rezo6BDi4uIEAILBYGAdh/SB7mm96OjRo5g3b56sj+pobW3Fww8/DIvFggMHDiApKYl1JPIjVLReUlNTgzlz5sBms6GoqAjx8fGsIw1Z9zef8vLyW97+hngX3dN6QfeCzcrKknXBAsDcuXPFc4IWLVqE1tZW1pFId2x75/JnsVjECfiBtmXpypUrxYUFRDqoaG+By+USFixYELADN9evXxeioqIEAILRaGQdh/yAivYWGAwGcXPxQF3iVl1dLXAcJwAQ8vPzWcchAo0eD9m+ffuwePFiqNVqFBcXY9SoUawj+UxBQQEWLlwIjuNQWlqK6dOns44U1Khoh6CtrQ33338/XC5X0Iyu7t69GytWrIBKpcK5c+cQERHBOlLQotHjIfj888/hcDjw1ltvBUXBAl0zptLS0mCxWPD666/T4V4MUUs7SI2NjZg4cSIcDodPNheXsra2NsTFxaG2thYZGRl48803WUcKStTSDgLP83jppZfgcDiQkZERVAULAGFhYTh48CA4jkN6ejoaGhpYRwpKVLQD5Ha78dZbb+HIkSPQarV49dVXWUdiYsyYMXj33XfB8zx+97vfsY4TnFgOXcvF9evXhaVLlwoABLVaLTQ1NbGOxJTD4RBiYmIEAEJOTg7rOEGH7mlvwm6346mnnhK3isnNzQ3oxzsDdfLkSWi1Wtx+++04d+5c0N0qsETd4344nU4sXboUJ06cgE6nw6FDh6hgfzB9+nRs2rQJDocDmzdvZh0nuLBu6qWqs7NTSEtLEwAISUlJATvj6VZ0dHSI0xwPHTrEOk7QoO5xHz7++GOsXr0aMTExOH78OMLDw1lHkqTS0lLMmTMHKpUKFy5cQFhYGOtIAY+6x704deoU9Ho9FAoF9u/fTwXbD61WC71eD4vFQt1kP6GW9keam5vx8MMPw2az4dChQ5g/fz7rSJLX2tqKCRMmwGazobq6GpMmTWIdKaBRS9uN2+3GihUrYLPZkJGRQQU7QCNGjMDWrVsBAKtWraLdHH2N7S21tHg2ZYuPj6djIAeps7NTSE5OFv/9aODOd6h7/IOysjLMmzcPAOhcmyFyOp1ISkrCkSNHkJaWhszMTISEhLCOFXCoaAFcuXIFU6dOhc1mQ2FhIRITE1lHki2r1YqJEyeKtxjBtqiA53k0Nzejra0NYWFhGDVqlPffuNg29Oy5XC5Bq9UKAITs7GzWcQJCdXW1uG/W3r17Wcfxmc7OTqGpqUmoqKgQ8vLyBJ1OJ+7y4fmIiooSMjMzvTr1Nehb2nfeeQdvv/02FixYgC+++IK6c17S/XygM2fOyGJE2el0ori4GBERERg2bJj4/y0WC6xWKywWCxobG/H999+jsbERp0+fBs/zPa6hUCgwffp0KJVKWCwWlJaWip/Lzs5GSkrKrQf1WvnLUG5urngaQLAvAvCF7OxssbWRw2kLnrwD/VAoFIJWqxVSUlIEo9EolJeXCy6Xq8c1LRaLkJubK6SkpAh5eXleyRm0LW33U+3k0hLI0dq1a2E0GhEXF4fCwkJJT1QpKSnBY489hiVLlmDatGn47rvvAACRkZHgOA6jRo2CUqnE8OHDERYWhhEjRjDJedtgvpjneZw9exbXr18HANx3330YN24cOI7zSThfaWxsRGJiInieR35+PhWsD2VmZqKpqQn5+flYu3YtcnJyJHsLcvfddwPoOmz7pZdeYpymHzdril0ul7B3715Br9eLgwvdP5RKpbBhwwbBYrF4pen3taamJkGtVgfk5uJSZbPZxH9zKQ/2lZSUCAC81o31lT6L1uVyCUajUVCpVD368EuXLhXS09OF9PR0QafT9fic1BdE22w2QaPRCACEtLQ0mkDhR5WVleLIamFhIes4vfKMcUh9xVKfRWs0GgUAAsdxgsFgEM6cOdPrLJempiYhIyND/IHs3LnTp4GHymazicc46vV6KlgGDhw4IL7Bm0wm1nF+YufOnQIAoaSkhHWUfvVatCaTSdxaZaDd3u470VdWVno15K3q7OwUj+/Q6XQ/GeEj/rNhwwZxRLm6upp1nB4yMzMl+fv7Y70WrWfou6ioaFAX83QvdDqdV8J5i+cXRafT0ZxYxjo6OsT9tpRKpaRatfT0dPkWbUpKigBAcDgcg7qYy+US74GlMjCVlZUl9hpsNhvrOETo6vl43kilNDjlKdra2lrWUfrV69K877//HgAwfPjwQY1EcxyH1NRUAMCxY8cG9b2+UFZWBr1eD6VSSYvZJSQkJAS/+93vkJ+fL/7ObN++nXUs/Otf/wIAyf+e9Fq0w4YNg0ajGdIFZ8+eDQD45ptvhp7KC5qbm7FkyRIAwMGDB+lZrAQtWrQIRUVF4DgOer0e+/btY5qno6OD6esPVK9FGxoaOuQLRkVFAQDKy8uHfI1b5XQ6kZKSArPZDKPRSKe8SZhWq0V+fj4AYPHixTh58iTjRNLXa9H+/Oc/7/Hnw4cPD/iCkZGRALr2WWLB7XYjNTUVX375JZYuXQq9Xs8kBxm4xMRE5OTkiP/d2NjIOJG09Vq0o0ePxnfffYf29naUlpbi0qVLA74gx3FQq9UAwGTbEaPRiD179iA+Ph7Z2dmSnTJHevK8wdpsNmzbto1JhjvvvBMApH8iYG+jUzabTYiPjxfi4uKGtHVIUlKS30eQOzo6xH2KlUqlcPnyZb+9NvGO69evCwqFgtmp8709pzWZTEJlZaVQX18vmQk5/U5jLC8vF65fvz7oi3r2CvLXw3OTySTExsYKAASNRiOLZWCkd4WFheKsKX8/NszLyxPnpOfl5YmbI3g+PNN4c3NzmS7l9Ml6Wk/R+uMhdX19vbiQQa/XD/rZMpEeT49pwYIFfm3dzGbzT3aeUKvVQnJysjgFtvuHXq9nMh1T1kXrcrnEBQBSX6xABq77qiB/T94vLCwU0tPThYyMDKGkpKTHm0ZLS4tQVFQkpKWlid34qKgov8+yk3XRerY8TUtL8+nrEP/zdJOjoqKElpYW1nF+wvO7B0A4fvy4X19btpuVHz16FKmpqVAqlTAYDKzjEC9LTExEcnIyzGazuBG6lHh2PQGAc+fO+fW1fVK0nudsvjqMqa6uDgkJCVAoFCgpKRGfDZPAsnHjRgDA1q1bUVNTwzjNDXa7Hb///e/FP3t2vPAbXzTfnoGhoYw830z3+53i4mKvX59Iy8aNG8XHeL09jXC5XILBYBDi4uKG/LQiPz9/wANKlZWV4pMKpVLJZHGB14vW4XCIw+Pe1tnZKS7rMhqNXr8+kZ7u5wSrVKqfFJdnYT2GuFrIYrEIHMfddPzFbDYLubm54uiySqViNhfA693j1tZWAD37/N6yb98+7NmzBxMmTMD//vc/mu4WBEJCQpCZmYm0tDRYLBYkJCSgubkZQNfMpffeew8AEBsbi4aGhkFf37N3cX+bE+7YsQNqtRrLli0Dz/NISUnBuXPnMGbMmKH9pW6Vt98FPO98vhjR9XSVPB8KhYImUgSJjo4OcU+yuLg4weVyib9r8fHxgtlsFuLj44WKigrB4XAIJSUlQnZ29k27zBUVFeKknJ07dwoVFRXC8ePHhdzcXMFgMIhrbD2vk5uby3xmlNeLduXKlT7bvKu2tlYIDw8XwsLCxH/IuLg4mlARJDo6OgS9Xi8AEE6fPi1uuFBeXi4IQtdzVE+xHTp0SDAajQMqMIPBcNONyTMyMnz91xswr25W3t7eDqVSCQBoaWnxyeixp/tdXV2N1NRUNDQ0wGAw4I9//KPXX4tIk91ux/79+7F69Wro9Xp8+OGHt3zNkydP4vDhwygrK0NrayseeeQRjB07Fk6nEwkJCZg1a5YXknuJN98BDh06JAAQkpOTvXnZPh07dkycmULHegSPzs5O8QmC1Pdz8gWvDUTxPI/f/OY3ACDuGOFrs2fPxpo1awAAe/fu9ctrEvaqqqpgMpkQFxc35B1W5GxARdvc3Izt27f3+4B79+7dqKqqglarRXx8vNcC3szq1avBcRzS09OZLbwn/uXZymjhwoWMkzBys6a4o6NDiIqKEm/Ie5vAXV1dLXZTWXRXPDsuxsTE0J7GAa6zs1NccVNRUcE6DhMDuqftfoZPbGxsj61ITSaT+HmWI2yehfdZWVnMMhDf8ywkUKvVQbuH9U2LtrOzUyxKz+qduLg4wWazCQ6HQ5zSxfqojdraWvEYE3p2G5gcDoc4ACXV84D8YUAtrad7bLFYxAfcsbGxYsHGxcVJ4l3PM/mCTsMLTJ6JDklJScwnOLB006JtaWkRuyOC0HNmCn6YSSKVxy3l5eXiG0ow/1ADUUtLi6BQKASFQhH0+3/ddPTYszNdZGQk2tvbUVZWhvPnz4uf5zhOMrvXxcbGIjY2FqdOnWK67zLxvoKCAjgcDixcuJDdnF+puFlVm81mcZ4vuk3r0ul04j2uRqORzDk5e/fupd0sAozNZhPHVfy9S4QUDeiRj2c5kkKhEOLj48XtLTs7O8XCHcpWq77Q1NQkcBwncBwnyTNQyeB5tjb91a9+RY/0hAEORFVWVgrHjx/v9R+s+2HNycnJkriX9AxYrF+/nnUUcotOnToljB49Wrjrrruolf2BV+Yed99NwmAweOOSt8RkMgkcxwlKpZJWAMmcZ9WYFH6vpMJrCwa6T7KQwiMXT7d97969rKOQITpz5ox4WyaVJxRS4NVVPtXV1WLhLl26lOnWlyUlJeK9NpGfzs5OcYd/muXWk9cXwVdXV4uTMaKiooQDBw4wuc91uVziiLcU980l/SsuLhbnB9AtTk9e3yNq0qRJOH/+PNLT02G327Fw4UJkZWV5+2VuiuM4PPfccwCAPXv2+P31ya05duwYAGDdunUYPnw44zTS4tWdK37MarXiypUriIyMxKhRo3z1Mn2qqqrClClToFQqcfXqVfrhy4TVakVUVBR4nkd9fT3GjRvHOpKk+PSEgYiICEyfPp1JwQKARqPB0qVLYbPZkJubyyQDGbzq6mrwPI+kpCQq2F7I9liQgfLspvH666/Tlqsy8Y9//AMAMG/ePMZJpCngi3bcuHFYv349eJ5HXl4e6zjkJtxuN4qKigB0bSdEfsqn97RS0dDQALVaDYVCgatXryI8PJx1JNKHjz/+GKtXr0ZUVBQuXbrU7ybiwSrgW1oAiI6ORkpKChwOB/bv3886DumD3W7HunXrAAB/+ctfqGD7EBRFCwArVqwAALz//vuSWUpIevrqq6/gcDiQlJSE6dOns44jWUFTtBqNBmq1GrW1tUM684X43kcffQTgxhss6V3QFC3HcXjssccAABcuXGCchvxYc3MzTpw4AYVCgccff5x1HEkLmqIFgDlz5gDoOkWeSItnL+Mnn3yS7mVvIihGjz2sVitUKhUUCgW+++47hIaGso5EfjBx4kTU1tYiLy8Pzz//POs4khZULW1ERATi4+PhcDhQUVHBOg75QUNDA2pra6FQKKDT6VjHkbygKloAePHFFwEAf//73xknIR6e41yee+45hISEME4jfUFXtDNmzAAAfP755/ToRyI8b6BPPvkk4yTyEFT3tB5TpkxBVVUVKioqEBsbyzpOULPb7VCpVOB5Hk1NTYiMjGQdSfKCrqUFgLVr1wIAHUQtARUVFeKKHirYgQnKon3mmWegUqmQn5+PgwcPso4T1CorKwEAM2fOZJxEPoKyaIcPH44PP/wQAJjsqkFu+OyzzwB07XhCBiYo72kBwOl0YuTIkXA4HLh8+TIdNcGA3W6HUqkEALS0tGDEiBGME8lDULa0ABAaGor169cD6BpJJv5nNBoBAFqtlgp2EIK2pQWAixcvYvz48VCpVLh06RLtIeVHR48eRUJCAniex/HjxzFr1izWkWQjaFtaoGtXC51OB4vFgi+//JJ1nKDhdDrx8ssvg+d56PV68dk5GZigLlrgxjKwnJwcxkmCR1FREUwmEzQaDYxGI82CGqSgL9q5c+dCqVTiyJEjuHjxIus4QeHAgQMAgDfeeIMKdgiCvmg5jsNrr70GAPjb3/7GOE1w8BQt7U4xNEFftADwxBNPALjxy0R8x263w+FwAAA9ZhsiKlp0PdhXqVQ4ceIE6urqWMcJaM3NzQCAqKgoxknki4oWXc9s09LSAAD5+fmM0wS2S5cuAQCmTp3KOIl8UdH+YP78+QC6RpFpyZ7v7N69GwCQmJjIOIl8BfXkih/zbHlSXl5OgyQ+4DlYCwDMZjMiIiIYJ5Inamm7efXVVwEAf/3rXxknCUyeg7USEhKoYG8BFW03Tz/9NDiOw0cffQS73c46TsDxvBlqtVrGSeSNirabiIgILF++HDzP46uvvmIdJ2C0t7djy5Yt2LVrFziOo83bbhEV7Y88/fTTALoOgiLesWbNGhgMBgDA1q1baYeKW0QDUT/C8zzuueceOBwOmM1mZgdiB4rW1lbce++9AIDi4mJotVqauniLqKX9EY7jsHLlSgA0Q8obrFYrAECpVGLu3LlUsF5ARdsLz8qfbdu2ged5xmnky+12i93iBQsWME4TOKh73Au3242xY8fCbDajsrISGo2GdSRZOnz4MBISEhAVFYWSkhKaa+wl1NL2IiQkRFxEcPXqVcZp5Gv79u0AgE2bNlHBehEVbR88uwMeO3aMcRJ5qqurE3cDoa6xd1HR9mHRokXgOA5Go1FcmUIGpqamBvPmzQMA6PV6hIWFMU4UWKho+xARESEujqeVPwPndDqRnJwMi8WC+Ph4bNiwgXWkgENF24/FixcDAD755BPGSeTj008/RW1tLTQaDQoKChAeHs46UsCh0eN+uN1u3HHHHeB5njbTHoDW1lZMmDABNpsNxcXFmDt3LutIAYla2n6EhISIi7U9kwRI3zZt2gSbzQatVkuLAnyIivYmHnvsMQDAN998wziJ79ntdlit1l7foNrb2/t943K73eKJAe+88w7NfPIh6h7fRGlpKebMmYPY2FhUVFSwjnPL2tvb0draCqvViurqajQ3N+PChQsoKSmBzWa76fcrFAqsWbMGCxcuxEMPPdTjVIYnn3wSc+bMwbp163z5Vwh6VLQ30f2gLikeeuxp/drb29He3g4AsNls4HkeISEhuPfee+F2u1FUVITNmzeLOyF6A8dxWLJkCWbPno3FixeD4zivXZv0jYp2AJ599lnk5+cjJycHERER4DgO06ZNQ0hICNra2sBxnNdGSdva2mC1WuF0OgF0nSbncrnE4qyrq0NdXR1aWlpQVVU1pNfgOA5Tp07F1KlT8dBDDyE8PBwTJ07EqFGjEBoaCqfTiba2tp98z/Dhw1FTU4NPP/0UBw4cgNlsFj8fGxuL8vJy6hb7ARXtAKSmpmLHjh39fo1KpcIvf/lLzJgxAzNmzEB0dDRCQ0MBdLWCbW1taG1tRUtLC9xuNzo6OsTdMTo6OlBTU4Nr167hyJEjQ8qoVCpx//33AwBGjx4tFt/Vq1dx7do1LFiwAGvWrEF0dLTX3mDq6urw9ddfY9u2bbj77rtx5swZKlo/oKIdgPfffx9paWlQq9V49NFH8e233+LUqVM+ez2O43D77bdj7NixiIyMhFKpFDdEGzlyJB544AEolUpERESILT9LbrcbbrebeY5gQUU7AHa7HV999RWeeOIJsZWyWq1it9jpdOLKlSuoqanBF198gSNHjvQ6qBMTE4Nhw4YhOjoaSqVSXBx+2223ITo6Gvfccw+mTJlCz4NJv6hofcRut4trcUNDQ2n+LfEaKlpCZIYmVxAiM1S0hMgMFS0hMkNFS4jMUNESIjNUtMTnPv74Yzz44IO0vNFLqGiJz9XV1cFkMgXF8kZ/uI11AF9ob29HUVERDh8+jI6ODgwbNgwzZszAM888Q7ONGBg/fjwA4Ntvv2WcJDAEVNE2NjbiT3/6E4xG40+WoO3ZswevvfYaXnnlFaSmpmLcuHGMUgafkSNHAsBPVg6RoQmI7jHP89ixYwfUajXeffddTJgwATt37sTly5dhsVjQ1NSEvLw8aDQaGI1GTJ48Ge+88464/I0QWRECwIIFCwQAgkajEcrLy/v92uPHjwsxMTECAEGn0wmdnZ1+Shm8du7cKQAQ0tPTB/29S5cuFbKysnyQSr5k39LyPI9hw4YhKioKn332GaZPn97v18+aNQunT59GUlIS8vPzsW/fPj8lDV4dHR0Autb8DkZdXR327NmD+vp6X8SSLdkXLVjs6OgAAASdSURBVMdxOHDgADIyMnD+/PkBfU9oaCjef/99AMBnn33my3gEQENDAwDg7rvvHtT3eXbGUKlUXs8kZ7IvWo+ZM2cO6pHCqFGjoNFocOjQIR+mIgDEtcURERGD+r6mpiYAwH333ef1THIWMEUbGRmJjRs3Dup7OI6j82f9oLGxEcDgW8zq6moAXW+w5IaAKVoAg9ruxG6349SpU4iLi/NhIgIAJ06cAIBB72TpaaHvuusur2eSs4Aq2sF49913AQALFy5knCSwdZ+6ONQN5by57WsgCMqi/fOf/wyj0YiYmBisWrWKdZygMJTBJM9mdi0tLd6OI2sBNSNqIKxWK1JTU6FQKHDw4EHau8nHWltbAdyYFTUYDz74IADg4sWLA/r65uZmmEwmOJ1OjB8/PmBPnw+qonU6nXj55ZfhcDiwc+fOgP2hSonb7QYwtPvS6OhoAMDp06fR2NiI8+fPw2q14tKlS6iursbZs2f7PMpEqVTi3//+99CDS1jQFG1bWxtWrVqFgoICaLVaLFu2jHWkoODp2g62e2y1WnHt2jUAwBdffIGCgoKbfo9SqcSsWbMwc+bMgD5mMyiK1ul0IikpCaWlpYiLi8P+/ftpY20/8bS0/WlubkZrayssFgtOnjyJsrIylJaWip8XBAE/+9nPMH/+fERHR2PChAkYM2YM7r333h63N+Hh4UHxcw34oi0rK4PBYMCpU6eg0+mwZ88e8bgO4nueU/W+//57uN1uVFVV4dq1a7h06RKqqqpQXl7e40yg7nQ6Ha5fv47i4mLs2rULzz//vD+jS1ZAF+327duh1+vFP7/00kt01oyfeeYbf/311xg5cmSv96AKhQJjx47F5MmTERsbi8mTJ2Py5MkICwvD7t27UVxcTGtxuwnoop08eTK0Wi3Onj0Lh8OBxx9/HCqVCh9++CEWLVrEOl5QiI6OhkqlgsVigc1mg1KpxJIlS6BSqTBp0iSo1WpxwKk3nqmP//znP/0VWfICumhnzZqFkpISOJ1OlJeX49ixY8jIyIBOp0NmZibS0tKo5fUxjuNQXFyMqqoqaDQajBs3blD/5t0PrSY/YL020N/q6+sFtVotABCMRiPrOOQmKisrBQBCcnIy6yiSEXQzosaNG4fi4mKo1WqkpaWhpqaGdSQyABcuXGAdQTKCrmiBrlUj69atA3Bj+RchchGURQvcWJhNK0ik7fr16wCACRMmME4iHUFZtIcPH8YHH3wAlUqFhx56iHUcQgYl4Iq2oaGhz53sy8rK8OyzzyIhIQE8z+Ojjz6iBQMS5+kJ0XPaGwLuUOlp06Zh/Pjx2L59u/i4oLm5GW+//TZ27doFoGvJ1yeffAKtVssyKhkAu90OpVIJjuPQ0dFBj+gQgEU7c+ZMnDhxAjExMUhMTMR///tf7Nq1Cw6HAyqVCtu2bcNTTz1FUxllZMqUKaiqqkJSUhKysrIGvQNGwGH7xMn7LBaLEB8fLwAQPziOEwwGg9DS0sI6HhmCiooKQaPRCHq9XnC5XKzjMBdwLa3HqVOnUF9fjxEjRgT0gmgSfAK2aAkJVAE3ekxIoKOiJURm/j9hT2O0Ssc5KAAAAABJRU5ErkJggg=="
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at a picture of a $5$-gon, we see that these two permutations correspond to a rotation and a reflection at the $y$-axis:\n",
    "![image.png](attachment:image.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus we expect (and can confirm) that the group generated by them is equal to the dihedral group with $2 \\cdot 5$ elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H.order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H.is_isomorphic(DihedralGroup(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's use this to try identifying a concrete group:"
   ]
  },
  {
   "attachments": {
    "image.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXUAAAEaCAYAAADuX8dHAAAgAElEQVR4nOzde0BU1dr48W8/dDyYSDEvyoSKqJMXpNASS9LwaHjSY5nSUbQ0b2mlZWVZp8zMrLwVpZbWMY90RC1I1NQgCVKRwtsEIREgMooM0IzgkHPaOi+/P3z3pIncZ/YMsz7/lMxlPyg8s/Zaz3rWDdXV1dUIgiAILcL/UzoAQRAEofmIpC4IgtCCiKQuCILQgoikLgiC0IKIpC4IgtCCiKQuCILQgoikLgiC0IK0UjoAQRBaLqvVSlJSEocPH0aj0QDQt29f7rjjDlQqlcLRtUwiqQuCYBe7du3i+eefJy8v75rH1Go1M2fOZOLEiQQHBysQXct1g9hR6rpyc3PZsWMHM2bMwMfHR+lwBMHmhRdeYOXKlQDMnz+fv/3tb1RUVGAymcjMzGTTpk2YzWYApk+fzttvv42vr6+SIbcc1YLLmjx5cjVQvWnTJqVDEQSbTZs2VQPVYWFh1dnZ2TU+p6Kionrr1q3VWq22GqjWaDTVmZmZDo60ZRIjdRe1d+9eRo4cCcDOnTsZPXq0whEJAhQXF9O7d298fHw4fPhwnaNvi8XCihUrWLRoEWq1mpSUFDEd00Si+sUFGQwGHn30Uduf27Ztq2A0gvCH5ORkzGYzy5Ytq9d0iqenJ6+99horV67EaDQyevRoiouLHRBpyyWSuouxWq088cQTGI1G29fUarWCEQnCH/Lz8wG49957G/S6559/npdeeomioiKmTZuGJEn2CM8tiKTuYrZt20ZCQgIBAQG2r4kFJsFZ+Pv7A1BVVYXFYmnQaxcvXsyoUaNISkoiOjraHuG5BTGn7kJyc3O57bbbkCSJzZs3M2nSJAB+//13UfMrOIUTJ04QFBTEzp07sVqtFBQU8Pzzz9f79QaDgf79+1NSUkJRURFdunSxY7QtkxipuwiLxcL06dORJImlS5dyyy23ABASEiISuuA0+vTpw5gxY5g6dSqvvvoqKSkpDRqx+/n52T4EkpOT7RVmiyY2H7mIt99+m7S0NCIiInj22WdZvXo1APfcc4/CkQnC1T777DPy8/Px9PSkR48eeHh4NOj1gwcPBuCHH35g6tSp9gixRRNJ3QXs3buXJUuWoFar+fTTT1GpVPzrX/8CICIiQuHoBOFq7dq1IyQkpMnvc/78+WaIxv2I6Rcnl5ubaytf3LZtG/7+/uh0OvLy8vDy8mLIkCEKRygIzeuzzz4DYOjQoQpH4ppEUndiJpOJcePGYTQa+fjjjxk2bBgABw8eBGDixIl4e3srGaIgNKsTJ07w8ccfo1ariYqKUjoclySSupOSJIlZs2aRnZ3N9OnTmTZtmu2xL774AoC//e1vSoUnCM0uNTWVu+66C0mSWLFiBe3atVM6JJckShqd1MaNG5k2bRqjRo3iiy++wNPTE7hcBSPvID158iSBgYFKhikIzSI+Pp7IyEgA1q1bx6xZsxSOyHWJpO6EUlNTGTFiBG3atOGnn366qlY3NzeXXr164eXlJRaSBJeXm5vLq6++SlxcHABbt25l/PjxCkfl2kT1i5PJysrigQceACAmJuaazRdnzpwB4I477nB4bILQHAwGA9nZ2Xz11Vd8+OGHSJJEQEAAW7Zs4e6771Y6PJcnkroTqaysZNy4cZjNZhITE2ssV/zpp5+Ay6fHCIKrqKqqYtiwYfz2229kZ2df9djixYt57rnnxBx6MxFJ3Ym8+eab5OXlsWbNmuvWn8uVLwMGDHBkaILQJJIkUVBQcFUjOtmiRYtYtGgRGo2G4OBgW4O6Hj16cPvttzN06FBxCEwDiKSuIJPJRH5+PqGhoSQlJbFy5UoiIiKYPXv2dV+j1+sB0cRLaF4WiwW9Xk9ZWRk///wzR48eta3ZqNVqNBoNM2fObPTPnY+PDwUFBXz++eecPn2ac+fOYTQaKSgoICcnB7PZTElJCSUlJTW+PjIykueee05Mz9SDWChVUHl5OVOnTiUwMJBNmzYBkJOTY+t0V5N+/fqh0+k4fvx4s+zaE1q+yspK9Ho9JSUlWK1WDAYDly5d4vTp05w9e5bKykoSExNtx8tdz5o1a3jqqafsFmNVVRXl5eUAVFRUYDQa2bp1q20RFSAqKop58+YRGhpqlzhaAjFSV9Dq1avZvXs3cHm7/8svv1xrQr+S6DctXI+8EKnT6Th48CB79uyp8+dFpVIxatQoevfuTY8ePbjtttvw9PTEw8ODsrIyRo4cydKlS5kyZYpd5r69vb3x9va+5ud/3LhxmEwmvvnmG3bs2EFBQQGpqakiqddCjNQVZDKZyM3NJTAwED8/v3q9ZsSIESQlJREXF8e4cePsHKHgrEwmEwaDgZKSEn799VfOnDlDTk4O+/fvJy8v76rnqtVqRo0aRUBAAK1atUKj0eDj40Pbtm3RaDSoVCq6dOlSa7KeOHEiW7ZsYfPmzUycONHe357QBGKkriAfH58GzxEOGzaMpKQkPv74Y6dN6vKHVWFhIb/99hvl5eX897//ve7z1Wo1N99883Xna2+66Sbb5quKigpKS0v59ddfKS0tBeDs2bNcuHCh3vHJ17tSr169CA0Nxdvb+6o4KisrARzejsFqtaLX6zlz5gynT5/GbDZz6tQpsrKy+P7772tccJSFhYXRr18/7rnnHoKDg+nZs2eDOyX+WY8ePQCa/D6C/YmkLjSaJEkYDAaOHTtGcnIyBw8eRKfTKR1Ws9FoNLaFO5VKRUhICN27dycgIIBu3brRvn17evTogZ+fX72nzeByws7KyiIzMxOz2UxpaSlnz54lKysLSZIoLS297oIhXP5QCgkJsU2VdO7cGR8fH7p3706PHj3sMj0iz7fv37+fuLg4Nm7cKEoQnZRI6i5m//79ALZTj5pLZmYmv/zyC+fOneP8+fP89ttvaDQaW5I5e/YsBQUFVFRUANSYvDUaDZGRkajVaoKDg+nWrRtqtRpfX1/bSPvPKisrsVgsNSaxS5cuYTAYrvm6n58fHTt2pF27dleVuvn6+tY4kpQkCZPJVOP1LRYLlZWVFBQU8OOPP1JUVMTFixc5f/48xcXF9O/fn/bt21NQUIBOpyMjI6Pmv8BmFhQUhFarZcCAAfj6+uLn50fnzp3x9/dXpPJJvitKTk4mNzeXp556ivDwcIfHIdRNJHUX8/bbbzN06FDGjh3bbO+5efNmHnnkkTqfFxQUROvWrYHLJWZt27ale/fu3Hbbbdx11131Xhe4kvwae1byqFSqOmMLCQmp13SWyWSivLycM2fOUFFRQUFBAdnZ2Vy8eJGcnBy6du1a4weY0WikrKzMFs+QIUO466678PLyokOHDraFQsDparLLy8tp3749AL/99htArdM/grJEUncxwcHBBAcHN9v7xcbG8sgjj3DDDTewZ88eQkND8fHxoby8nKqqKqxWK/7+/tcdabsbHx8ffHx86Nmzp9KhOIRer2fkyJG2XaBt2rQB4NSpU0qGJdRCJHU3Fh8fz9SpU2nVqhV33XXXVa18fX19xQYnN1dcXMzw4cPJy8tjzJgxPP744/j6+jJgwADbiF1wPqKfuhuyWq1s3LiRyMhIJEnizjvvFGedCjZWq5XY2FiGDh1KXl4ekZGRxMbGcv/999s2B2k0GoWjFK5HJHU3YzKZiIyMZNq0aahUKr744gu+//57Bg4cqHRoghNIT09n0KBBTJo0yTZCj4mJsU2//fLLL4BoU+HMRFJ3I3q9niFDhpCQkEBYWBiZmZnceOONAHTt2lXh6ARHq6yspGvXrqxatQpJkvjkk08IDw8nIyODkJAQUlJS2L59+1XrKQkJCYA4P9SZiTl1N2EymZgyZQrZ2dnMmTOH5cuX4+npSWpqKkCjKlcE1xUbG8u3335LUVEROp2OW2+9laKiIgBWrlzJ3LlzUalU17xOLmkVZ+M6L5HUWzhJkti6dSvLly8nOzubMWPGsGrVKtsvbI8ePYiKihK3025k1apVzJ8/3/bn+Ph4LBYL4eHhrFy5stYDWGpK9IKTqRZarEuXLlVHRkZWA9VAdWRkZPXvv/+udFiCQs6cOVO9Zs0a28/D22+/XT127NhqoHrlypX1eo/Q0NBqkTacmxipt2BLly4lLi6O8PBwNm3adM3ReIJ7WbJkCevXrwdg4cKFeHl58eWXXxIeHs6TTz5Z5+sNBgMZGRm2A6IF5ySSegu1atUqFi1aREBAAP/5z38a1JtEaHlMJhMbN24ELvdFnzlzJn/9618B+OSTT+q1uUxu2SDaAzg3kdRbGJPJRHR0NEuWLEGtVrNr1y6R0AUyMzORJAkvLy/bQRevvfYae/fubXBbAjGv7txEUm8hJEli8+bNPPPMM5jNZtRqNSkpKc3aUkBwTZWVlSxevBiAV1991fb1iIiI656FWxO58kVwbqJOvQUoLCzkr3/9K9OmTeP3339n2bJl5OTkiIQuAPDEE0+QmpqKRqNh1qxZjX6fo0ePAqL81dmJk49cWFVVFZs3b+bpp59GkiSioqJYunQpgYGBSocmOInc3Fx69eoFwM8//9ykRmT33HMPaWlpVFRUiDp1JyamX1xUeno6UVFRFBUV4eXlxSeffMKkSZPEyTTCVa5MvidPnmx0UrdarRw+fBitVisSupMT0y8uKCMjg/DwcIqKipgzZw45OTlMnjxZJHTBJjY2lnvuuYeAgAAAtFot/fr1a/T7eXh40KZNG7FI6gLESN3FZGVlMXz4cNtO0fHjxysdkuBk/rxjNCwsjNjY2CbPhXfv3r1FHVfYUomRugtJTU0lLCwMs9nMpk2bmjWhyzXMgmuTE7pKpWLz5s2UlJTw3XffNcvGM/nwafkwbsE5iaTuIlJTUxkxYgRms5l169YxefLkZn3/tLS0Zn0/wbGsVitvvfWWLaEnJiYyceJE/Pz8mm1aTj7K0GKxNMv7CfYhpl9cQHx8PBMnTkSSJPbs2cP999/f7Neo6YBnwTVYLBaeffZZ1q9fb0voYten+xJJ3clt27aNCRMm2H5ZG7JZpL6qqqpsJ9oIrsVisTB58mTi4uJQq9Vs376dwYMHKx2WoCCR1J1YbGwskyZNQqVSceTIEbttJtLr9XTv3t0u7y3Yj8lkYvr06SQkJKDVatmzZ49t3tsecnJyAHHqkbMTc+pOSJIk3njjDSZNmoRarWbfvn123R1aVlaGWq222/sLzU+v1zNs2DBbQo+Pj7drQgf47bffCAkJEaWzTk4kdSdjMBgYO3asrcNiSkqK3W+nCwsLxUHCLsRisTBz5kx0Oh1hYWGkpaXZvSWExWIhLy/Pdvyh4LzE9IsTycrKYsSIEZSUlDBq1Cg2btzokFvd06dP07lzZ7tfR2i6yspKZsyYQVJSEiEhIezcubPBXRYbe11A9OR3AWKk7iSSk5O58847KSkpITo6mi+//NJhc5fHjx/n5ptvdsi1hMaxWq3s3buX8PBw26Lo5s2bHZLQBdcikrrCqqqqeO211xg+fDgAiYmJPPPMMw7djn38+HFuvfVWh11PaBidTsftt9/OyJEjbVMu33//PX369FE6NMEJiekXBaWmpjJnzhyys7MJCAjg888/JzQ01KExVFVVUVRUJA7ScFI6nY6BAwciSRJBQUEsXLiQhx56SPRgEa5LjNQVUFxczMSJExk6dCjZ2dksXLiQn376yeEJHf7YdCQ67zkfvV7PP/7xDyRJYs6cORw7dozx48eLhC7USozUHchqtRITE2M7nSgsLIx3331XkWQuM5lMBAUFKXZ9oWYmk4kHH3yQvLw8IiMjWb58uaLJXP7QP3LkiGIxCPUjRuoOUl5ezoQJE2ynE61bt45vv/1W0YQOYDQabT09BOcgH3ii0+mIiIggJiamXgdD25OnpyeRkZHk5eWh1+sVjUWonUjqDnD06FHCwsKIi4tj1KhR5OXlMWvWLHEbLdRo9erVtpLFTZs2KZ7QZb179wYu30UIzkskdTuSJImNGzcyaNAg8vLyWLZsGTt27HCqWl+NRsNvv/2mdBjC/4mJibF1Wly/fr04D1RoMDGnbiepqak8/vjj5OXloVariY2NtUszrqby9vYmLy9P6TAELu9VmDJlCnC5kZvSU3N/Jm9QM5vNCkci1EaM1JuZJEm89dZbDB06lKKiIhYuXMiPP/7olAkdIDAwEC8vL6XDcHsmk4mHHnoIgJUrVzJmzBiFI7o+SZKUDkGohRipN6P8/Hwee+wx0tLSCAoKYsuWLXbvydEc7r77bqVDcGvl5eU89NBDmM1mIiMjmTdvntIh1Uhuzyyavzk3MVJvJgkJCfTv35+0tDSmT5/O/v37XSKhA2zZskXpENxWfn4+Dz30EGlpaYSGhrJ69Wqn7YIoV720a9dO4UiE2oiRejOQD7JQq9XExcUxbtw4pUNqENE/xPGsVitxcXHMnDnTtmfBUc25Gks+xk4kdecmRupNtHz5ciZMmIBGoyElJcXlErrgeBaLhUcffZQJEyZgNpuZNWsWX3/9tVMndPhj97FI6s7thurq6mqlg3BV8sntoaGhbN682e6HFAiu78rj5wICAvjoo4/scuZsc7NYLLRt25bQ0FB++OEHpcMRaiGmXxrptddeY8mSJWi1Wr788kvREEuok16v5+GHHyYjIwO1Ws2ePXtcptOi3E990KBBCkci1EVMvzRCfHw8S5YsISQkhH379omELtTpxIkTDB8+nIyMDEJDQ0lLS3OZhA5/7CIV5a/OTyT1BpAkiU8++YTIyEi8vLz46quvnGp3qOCcYmNj6devn605V2pqKj179lQ6rAYpKSkBoGPHjgpHItRFJPV6qKqqIjY2lr59+/L4448TEBDA/v37xQhdqFNycjKTJk1CkiQWL17M5s2bnaaXS0PIG45EvyLnJ+bUa6HT6diwYQObNm3CbDajUqlYuHAhc+fOddhRc4Lr0ul0jBw5EoBPP/2UqVOnKhyR4A5EUq9Beno6q1evtm3KCQgIYNGiRUyYMEGMzoV6iY+PZ+rUqUiSxLx580RCFxxGTL9cwWKx8MILLzBo0CC2bNlCREQE+/fvp6CggOeff77FJvRVq1YpHUKLYbVaefnll4mMjMRsNjN//nxWrlypdFiCGxFJ/f9kZGQwaNAgVq5cSWhoKEeOHCExMZHBgwc77bbt5lBZWUlSUpLSYbQYq1at4p133kGlUrF161ZWrFjRIn5+5HWA//3f/1U4EqEubj/9IkkSb775JkuWLAFg8eLFPPfcc26za06v11NRUaF0GC3CqlWrWLBgASqVitTU1BbVKE2j0QCXe9UIzs2tk3pxcTHTpk0jKSmJ0NBQPvzwQ+644w6lw3Ioo9EoWqk2g+TkZNvhFnFxcS0qoQO20t309HSFIxHq4rZJPTk5mfHjx2M0Gpk1axbvvfeeS5aaNZXcpEloPL1ez6OPPgrAJ598wujRoxWOqPnJvxvilCzn55ZJPSYmhilTpthGVe7chOvChQtKh+DSLBYLDz/8MCUlJUyePJlJkyYpHZLdaLVaTpw4oXQYQh3cKqkbDAaee+45tmzZglqtJiUlxWV6ntuLGHk1zYoVK8jIyCAkJIT33nuvRSyKXs+NN94opupcgNtUvxw4cID+/fvbShUPHz7s9gkdoFevXrZT4oWG2bZtG4sWLUKlUrFx40anb53bFJIkUVBQQEBAgNKhCHVo8UndarWyfv16hgwZgtFoZNOmTSQmJhIYGKh0aE4hNDSUNWvWKB2Gy4mPj2fChAnA5eQeEhKicET2ZTAYMJvNLXK9oKVp0dMvVquV+fPnEx0djVarJT4+XozOa9CSR5j2oNPpmDhxIgBbt2516kOim4t8QIY4M8D5XXekPnfuXJYvX+7IWJqVxWJh1qxZREdHExYWJubPhWZhMpls2/+XLl3K+PHjlQ7JIU6fPg2An5+fwpEIdakxqZtMJtasWUNycrKj42kWhYWF3HfffWzYsIExY8awc+fOFrvFX3CcwsJCHnjgAXQ6HeHh4Tz77LNKh+Qwubm5AKLVtAuoManLp5wMHDjQocE0ldVqZePGjfTq1Yu0tDReeukl4uLixPSC0GSpqakMGDCAtLQ0wsLCiI+Pd6t9DTfeeCMAv//+u8KRCHWpNam70lb5/Px8JkyYwLRp09BoNOzfv5+33367RZeYCY6xbds2hg4ditFoZN68eXzzzTduN1CQW02fPXtW4UiEutS6UHrzzTc7Ko5Gs1qtfPrpp8yZM8fW5vT111/H29tb6dCEFiA9Pd1W5bJp0yYmT56scETKkHOB2Nfg/GpM6maz2dFxNIpOp+PZZ58lNTWVkJAQNm7c2OJLywTHMRgMtt3G69atc9uELriWGqdfqqqqHB1Hg+h0OubOnUu/fv04dOgQCxcu5MCBAyKhC83GarUyY8YMSkpKmD59OrNmzVI6JEXJ7STat2+vcCRCXVyqTr2wsJC5c+eye/duACZPnszChQtF7azQ7GJiYti9ezdBQUHiEBEgOzsbQGzacwEukdQNBgMxMTEsXLjQVh88ZswY+vTpo3RoQgsUExPDtGnTgMvz6A1dn6mqqkKv11NQUIDBYKCkpIRLly4RFBREZGSkSy7ed+zYEbjcqllwbk1O6rm5uXh4eNhttJyUlMTo0aORJIlRo0axfPlykcybkSRJREdH8+KLLyodiuKsVitLly619XOJjY2tV3/9/Px8MjIyOHXqFN99912tJ0ktXbqUf/7zn80ZtkPI9enl5eUKRyLUpcak3qFDh3q/wfTp0zl8+DBHjhxp9h2bsbGxTJo0Ca1Wy4YNGxg8eHCzvr8AiYmJtltrdye3lNBoNMTHx9d60IXBYGDVqlXs2LGDvLy8qx4LCwujX79+9OrViy5dutCqVSuysrJYsGCBbROPq5FPPhJJ3fnVmNQbcnsob/SR61ibQ2pqKgsWLCAjIwOtVsu+ffvETjY7sFqtvPnmmzz11FNKh6K4Tz75xNYjqD4N33bt2mU7UDo0NJQlS5ag0WgIDAy8Zn+HxWKxtdwYNmyYfb4BO5Pr8jMzMxWORKhLk6df5LatBoOhWfpCJCcnM3z4cDQaDdHR0Tz22GOi5txOkpKSKCgo4MEHH1QsBrlRVEP5+PigUqkoLy/HarUClzfLNWbD3KpVq5g/fz5qtZqEhIR6LQY+8sgj+Pr6cuHCBRITE1mwYAFPPvnkNVODVquVF198kdTUVMLCwnj44YcbHJ8zkH+3f/75Z4UjEerS5KR+5swZgCZvma6qqmLz5s08/fTTBAUFkZKS0qyjf+FaSUlJREVF2e1D02QykZ+fz88//0xOTg5FRUXk5ORw7tw5ioqK7HLNkJAQ7rjjDttgo7Kykr/85S/06dOHrl27curUKb766isGDBjAXXfdxcqVK/nPf/5Du3btuP3225k0aRIvvPCCrQvj9Xh6etq6M06cOJHKykqOHDmCJElX/S4sXryYNWvWoNVqiY2NddnWAiqVCkAckuECmpzU5fnExm6bNplMREdHEx0djdlsJioqinfffVckdAc4dOgQs2fPrvfzLRaLrYXElSRJIjs7m2+//ZYjR45QWFhYZ9LWaDS2igrZjTfeaJtmu3jxYq0n1584cQK1Wk23bt3o0qULFouFAwcOoNPp0Ol0dX4vGzZsuOrPVVVVfPvtt6jV6kaV7Xl7e18ztbJq1SqWLFmCWq0mPj5eTCEKDlFjUpcXc+QmPrXZv38/arUab29vMjIyyM7OprCwkFatWjFkyBDCw8Nrff1rr73G2rVruffee3n99dcZPHiwS5Z8uRJJkjCZTGRkZPDYY4+RkJBAeXk558+fp7KykrNnz9o2mxQUFCBJEqWlpZSUlNT7Gl5eXnTv3p2BAwfSr18/evToQadOnfD29rZNndiDwWAgLy8Po9GI1Wqlbdu2/P777/zwww8UFRXRtm1bBg4cyPnz53nvvfcoKytjyZIl+Pj40KlTJwYNGtQsdy7ylI6Xl5do+yw4VI1J/fz580DdvV9OnTqF2WymW7du/M///E+N7QVSUlKum9gtFgtr164FLo90unXrJhJ6A1itVls1gsFgoKKiAqPRiMFgoLS0FICioiLOnz/PqVOnakzMTz75ZL2vp9Vqr/mgV6lUtG3bljvvvJMhQ4bQt29funTpoti/o5+fX41rO1ceZPH3v/+d++67j48++og2bdoQERHRrDG8//77tjn6uLi4FpPQNRoNFy9eVDoMoQ41JnV5lFbTaMpkMpGZmcn+/ftZsWIFACdPnkSj0TBlyhTuvvtuOnfujMVi4ddff6Vfv37Xvbinpydms5n169fzz3/+k759+7JmzRr+/ve/4+PjY1sEq8/IzmKxUF5ejslkqnFE+fvvv19TjtWpUyfb/6vVajw8PCgrK7vqOefPn7d9yF2pTZs2+Pr60q5dO7y8vIC6DxCorKzEYrFcN/6KigoAzp07x6lTp/jvf/+L2Wy2JWi9Xm9rqNSUeWm5nYK/vz+9e/emU6dO3Hzzzdd8P/Lfu4eHR4uZDrNarRw7dozdu3dz8uTJZt8hmZCQwLx581rcweYWi4Wqqiq73WEJzeeG6urq6j9/8Z577iEtLY0zZ87g5+eHTqdj9+7d7N69m4yMDNvzOnbsSGlpKREREezZs6dJozOdTscjjzxSY820SqUiPDyc2267DU9PT8rKymyJVq/Xc/jwYbddwAkJCaFDhw74+fkREBBAx44d8fPzo23bttx00014enri4eGBv7+/27WLrYkkSba7yoqKimZfJL711lvJy8tDo9Ewfvx4evXqRWlpKZcuXQKwLdC62oekwWBAo9EQFRVFbGys0uEItbhmpF5cXExaWhpeXl688847HDx48KqFp9DQUB588EEGDhxI9+7dCQwMtI1ymyIkJIRjx46RmJjIt99+S2lpKW3btsXX15djx46RlJR03Z16ISEh3HjjjXTv3p2AgAD8/f35f/+v5pP6fH19adOmDfBH5aJFyR0AACAASURBVI48l/xn7dq1q3UK6srX1baoV5fWrVtfdUq7v78/gYGBV20C+3O5njhWrHFMJhNms5mQkBC7VP089dRTvPfeexQVFREdHV3jc1QqFYsWLWLBggUuM90oj9BrumsVnMs1I3WDwUBAQMBVI9+oqCgee+wxBg0adFViceSnt8ViQa/XY7FYrkpoIrkJDZGfn49WqyUkJITjx4/b7TrFxcXk5eWh1+tp3749bdq0sS3Yrl27FrPZzPbt213q0Oor7+DF8ZDO65qRup+fH0eOHKGiosJ2W3+9EU1xcTFAo/+Bjx49ikqlqte8o6enJz179mzUdQRBJg8CTpw4Ydfr+Pv71/h7MWbMGC5dusTKlSttm6ZcRVRUFGlpaWRmZoqk7sRqXCit7+KOvKjYmGZeer2eO++8k4CAAE6dOtXg1wtCYxQWFgIo1hTu6NGjfPDBBwD0799fkRgaS14XEJxbzRPPDX2T68xfX48kSbbKmVdeeaU5QhCEesnKygJg9OjRilx7xIgRSJLEmjVrXK43+Z49ewDo1q2bwpEItWlSUm/sJ7dKpeIf//gHIE5SERxLTqT2alNwPTqdznZ4dVRUVIN28joLtVoNIHoxObkmJXW5GdOV9d71JR+ZJ5K64Ehy7xVHbaKxWq2sXbuWgQMHYjQamTdvHhs2bHCZqpcrtW3bFrhcQSQ4ryYl9dOnTwN/fII3hPxBcPLkyaaEIAhOKysri+HDhzNnzhwkSWLhwoWsXLnSZZt6DRgwAPijFFhwTk1K6nJtdmN2mfXs2ROVSsXOnTubEoLQBLm5ubYKJnfhiIoT+Szd2267jdTUVAICAti3bx9vvPGGS47QZTfddBPQ+HbJgmM0qUujfAvbmJGHSqVi5MiRJCQkNCUEoQnWrVvH3//+d7cqT2tKxdb16PV6ysvLOX36NJ9//jnx8fG2fR6LFy/mmWeeaRHz0PJGvHPnzikciVCbRid1q9VKSkoKarW6UfXjVVVVJCcnExQU1NgQhCawWq3s3r2bKVOmKB2KQ8mjTbkKpqkkSUKr1V61WU+lUjFnzhyeeOKJFnWerrzrOScnR+FIhNo0Oqnn5+djNBqZPHlyo15/6NAhzGYzzzzzTGNDEJqgsLCQvLw8t9uRK1e/NNfeCJVKRUxMDHv27OHixYsMHDiQyMjIFnn3c/ToUeCP084E59TopB4YGEhAQABGo7FRr5fnFv/3f/+3sSEITeDokr6WbPz48YwfP17pMOwuMTERgPvuu0/hSITaNHqhVKVSsWHDBo4dO3bddrK1kVvyfv31140NQWgCebqgJcz1NoS3tzdeXl6cOHHC7RaJm6p169ZA4wojBMdpUvXLsGHDOHv2bKMWSuU2sKJFgOBInp6ePPXUU0iSRHJystLhuBS5fchPP/2kcCRCbZqlTUBjqdVqcZKKQrRaLeCe5WnyYSmu1tNcafJCqWi/69wUTeqdO3dGr9crGYLbCgwMRKPRuN3mr9zcXNuh0/IHm1A/v/zyC9D4rqyCYyia1HU6nVhJV4iHhweLFy9uVIsHVyav/4waNapZa9XdgXxYjvgwdG5N2nzUFHIL1NDQUKVCcHszZ85UOgSHk0sa9+/fjyRJYtGvAeR2IO56dKSrUGykLrfxHDlypFIhCG7I29ubkJAQzGazW64nNIW8o1Ruxic4J8WSemlpKQAajUapEAQ3JU8jiIXShjl79iyAS/evcQeKzqkLgqNduafCVbslKsFgMLBhwwa0Wm2Lan3QEimW1OUOj652+ovg2rZv3w5ASEiIwpG4lu+//x6A559/XozUnZxiSd1oNOLl5eV2OxoFZXXu3BmADh06KByJa5EP6r7tttsUjkSoiyJJXZIk0tPTufvuu5W4vODGvLy8gD9a8Ar1I1e+yGthgvNSJKmbTCbMZnOjTkwShKaQN86I5NQwXbp0AcTfmytQJKnLfV8KCgqUuLzgxuSKl5KSEoUjcS3ydJVogub8FEnqKpUKrVYrPvUFhxMbZxpHvsM5duyYwpEIdVFsofTWW2+lqKioUW17heaj1+vdqv+O2EHaOPJhKmKk7vwUS+pyG093SijORj7h/vDhw0qH4lByt0Gxo7T+5M6Wol+O81MsqcsN98VIXTm5ubnExMQwevRopUNxqHvvvReAzMxMhSNxHVarFfjj91ZwXmJHqRv75ZdfCA8Pd7spCXmkLo70qz95w1Fjj68UHEckdTfWtm1bLly4oHQYgguQq4ZEfb/zE0ndjYndgUJ9ydMv7nZX54oUS+ryra9oE6Acf39/9u7dq3QYirnxxhuVDsFlyAul3bt3VzgSoS6KJXX5bNJ27dopFYLAHxvB3Ik8hSD3BxfqJlcKdezYUeFIhLooltTlHX2ip7XgaPJxbGfOnFE4Etdx+vRpAHr16qVwJEJdFEvqWVlZov2poAh5IHH+/HmFI3EdWVlZgKhTdwWKtt4V7U8FJcjNqXJychSOxHXId9YVFRUKRyLURZGkfvToUUBUXwjK6NSpE/DHz6FQt0cffRSA+Ph4hSMR6qJIUt+xYwcAY8eOVeLygpsTi/MNJ5c0Cs5P0Tp1Uc6oLEmSSE1NVToMhxOtKRrGYrEwbtw4APr27atwNEJdFEnqcjIXn/7KysrK4v3331c6DIerrKwE/mgnK9ROkiRKSkrQaDTMnz9f6XCEOiiS1JOSklCpVGIlXWFlZWVkZ2crHYZifvvtN6VDcAne3t6MGTOGkpIS24HxgvNSJKmnp6cTEhKCp6enEpcXrpCXl6d0CA4nlzTm5uYqHIlr0Ov1/PDDD4B7blZzNQ5P6uXl5ZjNZrHd2AnceeedhIaGKh2Gw/n5+aFSqSgpKbFtfxeu7+DBg5SUlBAVFWU7LENwXg5P6j4+PqhUKnE4hhPw9fXlwIEDSofhcB4eHraFP9FTvW7yztvHH39c4UiE+nB4Uvfw8KBPnz6kpaU5+tLCn+Tn5/POO+8oHYYiwsLCANDpdApH4vzkFgEajUbhSIT6UGROvbS0lKCgICUuLVzh6NGjdO3aVekwFNGtWzdAjNTrQz4YQ6yBuQZFknpJSQm9e/dW4tLCFY4cOWJrbuVu5A1IcrdQ4frkKjWTyaRwJEJ9KH5GqaCcffv2uW1ZqVqtBkRTr/qQ2+2eOnVK4UiE+hAnH7mphIQEzp0757atj+XSvOLiYoUjcX7yVFVpaWmNjxcXF4tduk7E4UldkiRHX1L4kxMnTjB+/HheeOEFpUNRnLwIKFxft27dUKlUrF69+prHDAYD3bp145///KcCkQk1cXhSl09QkW9/Bcd78803AYiKilI4EuXJi4DC9fXs2ZOpU6des1GtqqqKuXPnioGak3F4Uj958iQgmu0rKScnhz59+ojdgUK9BQcHX3WojdVqZf78+cTFxREaGsrs2bMb9H4mk4kTJ06I/k924PCkLn/ai+oX5YSHh3PixAkKCwuVDkUxojyv/qxWK/369ePll1+2/XnatGmsX78erVbL3r176dmzZ73fLz4+nr59+xIUFCT2CdiBw5O62MigvPnz5zNo0CB27typdCiKEW2f6+fAgQPMmjWLVq1aMWbMGADWrVtHTEwMoaGh7Nu3r953fFVVVcyePZvIyEhKSkpYvHgxffr0sWf4bqmVoy949uxZQBw4rSR/f39SUlKa/X2tVisHDhwgMTGR1q1b065dO/773//SqlUr23+7du1KRESEYj1EysvLKS4u5qabbqrxcb1eT1FRERUVFRgMBk6fPo3FYrFVyRiNRsrKyrh48SIzZ87knnvuISQkBA8Pj2aNsbKyEh8fH4dMkeXn52OxWDAajWRnZzNw4EDKy8s5d+4cZ86cYfXq1bY7m127djFnzhxUKhUbN260HQ1Yl6ysLMaNG0deXh4hISFs3LhRnFFsJzdUV1dXO/KCDz/8MHFxcVy6dKlZfxGE6zOZTKSlpTF69Oh6v8ZgMODp6XndEW1VVRWHDh2iqKgISZIwGo14e3vTt29fhg0bds3zLRYLlZWV5OXl8eWXX1JaWsodd9zB888/3+jvqybl5eUcOXLkqq9duHCBgoICdu7cSVpaGuHh4cybN48xY8Zw0003cf/992OxWLh48SKtW7dGrVZzyy230LlzZ+By+WPbtm1td5d+fn6YTCa++uor0tPTSU5OZuLEifTu3ZvevXvToUMHPD09CQwMRKVSYbVayc3N5cCBA2zdupXc3FxUKhUDBgygdevWFBQU8I9//MP2d5Gfn8+PP/7IqVOnyMvLw2g0MmHCBMaNG0dsbCwdO3Zk0KBBtkRrMpkoLCzk7NmzjB49muTkZL777jv8/f3573//S1ZWFhcvXqR9+/a0a9eORx99lD59+mAymVizZg1qtZpLly7RqlUr7rrrLtsHrslkok+fPrbf05iYGKZMmQJASkoK4eHh9fo3ycrKYujQoRiNRqKiovjoo4/EnZIdOTyp9+3bF4PBwK+//urIy7odSZLQ6XT8+OOPxMXFkZqaSllZWb1/mV577TWWLFlCZGQkDz30EH369KGsrIyioiL27NmDWq3mwQcfZMCAAbRr165Zj4jT6XRs2LCBrl27EhoaSr9+/UhMTOTHH3/E29ubTp06cd9999U4ii0vLyctLY1ffvmF7Oxs247Rjh07cttttzF48GB69OhBfn4+Wq2W8PDwZrlr0ev1lJeXk5ubS35+PpcuXeLYsWN8//33GI1GNBoNYWFhTJgwwVb5VVhYyKVLl+jUqRPh4eHXnee3Wq1IkoSnpyd6vZ69e/fy5Zdf4ufnx4ULF9i5cyeDBg3iueeeq/OD22q1snTpUvR6Pb6+vsyZM6fOw0Lk1yxatAiVSkVcXFy9BwiFhYUMGDAAo9HISy+9xJtvvikGc3bm8KR+ww03NNsvklCz3Nxcxo0bZzsAQ6VSsWbNGmbOnFnv99DpdHh7e3Ps2DHi4+PJyclh4MCBDBo0iPDw8HrfdjdFcXExhw8fJi0tDU9PT9vIGWDEiBFNiiE9PZ1BgwYRFRVFbGxsc4TrcHq9HoPBQEhICCqVyi7XsFgsTJ8+nS1btqBWq9m+fTuDBw+u12srKyuJiIggIyODpUuXilp2R6l2ILPZXA1UR0VFOfKybqOoqKg6Ojq6WqvVVs+bN69637591UVFRdVGo1Hp0JzOnj17xM9iHS5cuFAdGRlZDVQHBQVVFxUVNej18+bNqwaqIyMjqy9dumSnKIU/c+hCaVVVFQDt27d35GXdwmuvvca5c+cYN24cP/30k91GbteTm5uLv79/s07DOILYL3F9c+fOJS4ujrCwMHbu3NmgRdvk5GSio6PRaDR8+OGHYsrFgRTp/dKhQwclLtviZGVlMWPGDPR6PW+88QarV68mPDzcIQm9srKSo0ePsnHjRoYOHUqvXr1Yv3693a/b3MrKypQOwSktX76cDRs2oNVq2b59e4MSelVVFdOnTwfg3//+t6h0czCHjtTFduLms3HjRqZNm8bChQvrXOiSJScnEx8fz5tvvlnvX9LKykqKi4vJycnhyJEj/Pzzzxw/fpyioiLbc9RqNUuXLmXy5MmN+l6UJLo0Xis2NpYFCxagVqtJSEhocFLesmULRUVFTJ8+nYiICDtFKVyPQ5O63I/Z1W7RnU1CQgLTpk1j06ZN9U6kkiTxyCOP8Ouvv7J9+3bmzp3L0KFD8fT0pKSkhDNnznDhwgVbHfbx48fJycnBbDZf814qlYqQkBD+9re/MWTIkForNwTXsm3bNiZNmoRKpSIxMbHBm4MkSWLFihUAPPfcc/YIUaiDQ5O6fKsrbscar7KykhkzZrBy5coGjYxPnDiBwWAgMjKSxMREXnnllXq9LiQkhB49etCvXz+Cg4Pp3bs3/v7+Iom3QLGxsVcl9DvuuKPB75GYmEheXh4RERFit6hCHJrU5Q6N4kTyxrFYLLz++usEBwczd+7cBr32+PHjwOUOjdHR0YwYMYL77ruP0tJSevXqRVBQEG3btgXgpptuIjAwUPw7uZErR+j79u2rd9nin8XFxQEwZ86cer/GarVSXFyMyWTC399fDPqayKFJ/ffffwdE35fGOnToEL6+vsTHxzd6MVSSJPz9/fn0008JDQ1t5ggFVxQfH8+ECRNsI/TGJvSqqiq2bt2Kl5cXw4cPv+7zDAYDSUlJmM1mjh8/zmeffXbVetvkyZN566236r1WJFzNoUldLEo1zbBhw2rcgl8f8qj7zJkzBAcHi4QuAJc3mU2cONGW0Ou79b8mer0eSZJqXGORJInt27fz2WefsXv37qse8/LyYsCAAXTv3p3vvvuOmJgYdu/ezU8//STuFhvBoUm9srLSkZcTrnDu3DmlQ3AqYrH+cgfGhx56CEmS2Lp1a5MSOvxR3fbnA3Dk0tuMjAwAtFots2bNok+fPrRr145+/frZ/j0qKyvp3LkzRqORzMxMkdQbwaFJXT7AVri+jIwMSktLG9R8qz7kKhYx9XWZOx88bbVaiYmJYfbs2UiSxMqVKxk/fnyT31eeLjl06BBwOclHR0ezYMEC4PI8++OPP05wcHCNr6+qqmLGjBmYzWbGjBnDoEGDmhyTO3Lo5iN5HlicdlKzAwcOMHjwYLv8/YgDlq/mrgdPGwwGHnzwQaZNmwbAxx9/3GydMn19fQkKCqKoqIhdu3YxduxYFixYQGhoKD/88AOrV6+uMaFbLBaSkpIYNmwYcXFxjBo1itjYWHE31UgO76cOYhdfTY4ePcqoUaMIDw9v9lH6lf4812kymcjMzLzmNPigoCCHNO0SHCc3N5ehQ4dSUlJCWFgYH3/8cbOXHa5YsYKRI0fywAMP2BrJzZ49u8Y2AZWVlXz++ecsXbrUtplt1qxZvPfee6JktgkcmtQ7derkyMu5FD8/P/bv32+3gwPkFrRy693i4mIWLVrEhg0brvua+fPn8+qrr4re1y2AyWRi9OjRthOHXnrpJbu0k7j//vuJiopiy5Yt9OnThwEDBmCxWKiqqqK8vNy2ye3IkSOsXbsWs9mMSqVi3rx5jB07ttGVN8IfFBmpC9fy9/e3WwmX1WolPj4eLy8vfHx8SE9PJyoqiqKiIoKCgpg8eTI333yz7fmSJPHRRx+xcuVK9u/fz44dO8SClQuT2+fm5eUxZ84cXnnlFbs22HrnnXe4ePEicXFxDBw48LrP02g0LFq0iLFjxxIYGGi3eNyNIkndHRenlOTh4YHBYKB79+6sXr2a+fPno1Kp2LRpE5MmTarxF3zatGk8++yzrF+/niFDhrBv3z4xHeOi/vOf/5CQkEBYWBjLly+3e8fELl268MUXX5CUlMQnn3xCfn4+/v7+qNVqgoKCuPnmm+nWrdtVpzcJzciRfX73799fDVR//PHHjrysUF1dPX369GqgGqgOCAioPnLkSJ2vuXTpkq0n9uTJkx0QpeOUlJRUA9UajUbpUOwqJSWlWqVSVatUquqTJ08qHY7gAA6tfvHy8nLk5YQrvPLKK0RERDBnzhyOHTtWr74eHh4ettNqMjMz7R2iIkpKSpQOwW6OHj3KiBEjkCSJ2NhYMcXhJsScup0VFhbywQcfsG3bNnJychRbdAwMDCQxMbHBr4uJiQGoddu3K2rp5XKpqalERkbaNhaNGzdO6ZAEB1HkkAx3UV5ezoABAzCZTHz//fcuV0WSnp7O/PnzUavVzVbL7CyuTOotad+E1Wpl+fLlDB06FKPRyJo1a5plY5HgOsRI3Y6++eYbevXqxaZNm5QOpcGysrJs9fKfffZZi6x+CQoKIjs7G4PB0CKaR5lMJqZPn05CQgIajYZt27aJEkE3JEbqdmK1Wvnwww95++23lQ7lKvUZlWZlZdlGetHR0dx///0OiMzxWrduDVy+o3J1BoOBBx54gISEBEJDQzl8+LBI6G5KkaTuDiWNHh4efP311073i7V06VLmzp173eZq8fHxhIWFYTQaWblyJc8884yDIxQaKj09nbvuuou0tDQiIyNJTk5uEXceQuMoMv3iLt0anXExbtSoUQwaNIj4+HgWLFhAt27d8PLyok2bNqxbt46YmBhUKhXr1q1j1qxZSocr1EKSJNu+A8CuO0UF1yHm1N3MHXfcwYEDBxg5ciTz5s275nGtVsvnn39ut3YFzqRDhw5Kh9BoxcXFPPLII6SmpqJWq4mNjRWHPAuASOpuKTQ0lB9//JHk5GTy8/M5d+4cf/nLX+jTpw9jx451uSqdxvpz329XodPpGD58OEajkVGjRvGvf/2rRS5kC40jknoTSZJEZWWly52r6O/v36CDqwXnkJ6ezujRozEajSxbtoznn3/e7tv+Bdciql+aQO58t3DhQqVDERpB7lzp7PLz85k9ezY33HADgwYNwmg0snXrVl588UWR0IVriKTeSJIk8cADDwDw3nvvKRyN0BhySaN8KpSzsVgsvPbaa2i1WtavX4+XlxdhYWHs2bNHbCgSrktMvzTSrl27OHz4MCdPnhSd5lxU3759Afj555+drvQUYPXq1SxZsgSNRsM777zDhAkTRGWLUCeR1BuoqqqK9evXs3jxYt566y1RD+zCunbtCsDp06cVjuRaVquVLVu2AHD48GHxcybUm5h+aYA33niDrl278tVXX7F9+/YaSwIF13HlwSDOpLy8nPnz56PT6RgzZoxI6EKDiJF6AzzzzDNic4dgN7m5ubz66qvExcUBl/cMvP/++wpHJbgakdQbwF3qtwXHi42NZerUqUiShFar5ZFHHmH69OlilC40mEjqgqCw9evXM3v2bFQqFR9//DHTpk0TpYpCo4mkLrgtg8EAQKtWyv0aVFZW8vTTT6NWq9m3b59btGcQ7EsslApu69KlS8DlU+2VYLVaef3115EkiSeffFIkdKFZiKT+fywWCxs3bmTKlClKhyI4iHw+qY+Pj8OvbTKZeOqpp4iOjkar1fLkk086PAahZRJJHdi4cSOdO3cmLS2NtWvXKh2O4CBnz54FHN/Y68CBA/Tv35/169cTFhbGvn37REMuodm4dVIvLy9nypQpTJs2jXfffZd//etfTtkDXbAP+bCWNm3aOOR6kiSxatUqhgwZQlFREQsXLuSbb76hS5cuDrm+4B4UWSHq2LGjEpe9SmpqKhMnTgRg3759DBs2TOGIBEeTfw4rKirsfi29Xs8zzzxDQkICarWa7du3O2VrAsH1OXSkLjdOUnrzTlJSEiNGjCAsLIzDhw+LhO6m5AXSc+fO2fU6e/fupX///iQkJBAREcGxY8dEQhfsxqEjdaPRCCizMCXT6XQ89thjfPDBB8yYMUPUA7sxeR5bXjC1h9jYWCZNmgTAunXrxM+cYHcOTeryqe1t27Z15GUByMrK4v333+eWW25hz549onxMsB1sIterNyer1crixYtZsmQJarWaPXv2EBoa2uzXEYQ/c5vNR0ajkejoaLEQKtjI0y/FxcXN+r5Wq5Vly5axZMkStFotCQkJ9OnTp1mvIQjXo0hSv+mmmxx+zfDwcIdfU3Bu8jRgQUFBs77vq6++yjvvvINarSYxMZHAwMBmfX9BqI1DF0rlBSlHHCpRXFxMcnKy3a8juC65QVtz9lNftWoV77zzDlqtlsOHD4uELjicQ5N6VVWVQ65z4MABhg4dysmTJx1yPcE1yUm9pKSkWX42d+3axfz589Fqtezbt08kdEERLWbzkclk4q233qJfv34MGTKEBx98kJkzZyodluDk5AVzeRG/sdavX88DDzyASqUiPj5ebCgSFNMikrpOp+Ouu+7i3XffJSoqikOHDrFixQqlwxJcgNyvvLFJPT09nRkzZjB79mxbp8Xg4ODmDFEQGsShC6XynHpz9bmoqqrigw8+4JVXXmHUqFHExMQoWgMvuB6tVgtAfn5+g0oOc3Nz2bx5M0uWLAEuV9IkJiaKhC4ozqFJ/cyZMwDNsvniwIEDPP3009x4441im7/QaD169ADqP1K3WCysXr2aBQsWABAQEMBHH33E4MGDRbms4BQcmtSPHz+ORqOxbfpoitOnT7N+/XqxoUNokl69egGXN6fVRT7QIiYmBq1Wy/Llyxk+fLhI5oJTuaG6urraERcqLi6mU6dOjBo1iq+++soRlxSEOsk/lxqNxtaKtybJycnMnz8fnU5HREQEW7ZsEVN9glNy2EKpfHvbv39/R11SEOokL5SWlJRgtVqvebyyspIXXniB4cOHo9PpWLx4Mbt27RIJXXBaDpt+KSsrA5yj7a4gXMnLywuz2Ux5eflVi/jFxcWMHTuWjIwMwsPDWbt2rdjuLzg9hyV1ub9Gt27dHHVJQaiT1WqlXbt2mM1mVCoVWVlZnDp1ih07drBhwwYAFi9ezAsvvOCQndCC0FQOS+o//PADIJK64FxOnDhBSUkJISEh+Pj4MGfOHLZs2WJ7fNmyZbz44osKRigIDeOwpP7111/j5eUltk4LTsNqtbJr1y4ARo8eDcC///1vXn75ZaxWK56envTs2VPJEAWhwRxW/XLrrbeSl5dHbZezWCx8+umnjBs3ThzEK9hYrVbKy8upqqqiqqoKs9l8Ta8WuY2uj49PjSdrlZeX2xZCJUni8OHDfPTRR2RnZ6NSqcjMzBQJXGgRHDJSt1qtFBUV1XowhclkYtasWaSkpDBy5EhHhCU4AZPJRHl5OWfOnKG4uJjff/+dCxcu2P5cUlJCamqq3a4fFhbGggULREIXWgyHJPWkpCQkSeKee+6p8fH8/Hwee+wxDh8+LLrbtUBVVVWUl5djMBjQ6/Xk5uaSkZHB999/bzvisDZqtZrg4GDbaLx9+/Z06NDB9vjFixcpKioCLvdGlyTpmvfo2rXrVQudYWFhDBkyRGzrF1ochyT19PR0AKZPn37V1/Pz83n55ZeJi4uzHSggDuR1PVlZWRw5coRLly5x4sQJTpw4wdGjR+uVsENCQujRowd+fn706NGDtm3b4uvrS9u24k/UagAACdVJREFUbenQoQPe3t506dJFnOspCPXkkKQuV77I7UgrKyvZsWMHM2fOxMvLi+joaB577DFbf2uheRkMBts5nN7e3nh6etKuXbtat7frdDo2b95c51FvmZmZZGdn1/qcoKAgtFotPXr0oFOnTnTr1o3evXvTpUuXGue/BUFoPLsndavVSm5uLiqVivLycubMmUNOTg46nY7p06ezatUqkcwboLCwkH379pGSkmL7e5QFBQUB1Jlk/0ytVuPn59fg18nCw8OJjIy0VTdptdrrLlgKgmBfdk/qhYWFFBUVMXnyZHr27MkTTzxBSkoKycnJbr3VWq7kgKtPs/f397+q4ZnFYqG4uJgzZ85w6NAhFi9eXOOcMdSczFUqFeHh4ajVatvXcnJybP9/7tw5ioqKMBqNqFQq245Jf39/pk6dSt++fWv80JXj79Kli1v/O8qKi4v56quvKC4uxmw2U1paanusV69ejB8/XizGCg5h95JGnU5Hv379UKlUfPDBB8yYMcPl5kflRT65JM5qtVJWVobBYODSpUu250mSxJkzZ2yLdnA5KZ86deqqEXVdAgICuPnmm20J90peXl68/fbbDBgwgJ49e4q7HIWdOHGCb775hhdffPG6H7Zw+d+ttLRU7EoV7M4hdeobN27klVdeoaSkBK1WS15eHqGhoTz44IPceeeddOvWzTa/K8/51sZisWAwGKisrLzuczw9PfH29qa8vJyKigrbqPjkyZO2UdS5c+euu5hnNBopKyujoKAAs9ncmG/7Kl5eXnTv3v2ar19ZldG6dWv0ev1VJXyhoaEEBwfTrVs3unbtyn333dcsrYuF2q1atYqDBw/Sq1cvgoODCQwMxNPTE7PZTEVFBXq9nri4ONu/VXh4OMuWLaNLly74+vraBi4DBw4kIyOD6OhonnnmGSW/JcFNOGzzkcFgYO7cucTFxaHRaCgpKXHEZZssICCAvn370rt376s+bP7yl79ck1x9fHy45ZZbrqnWkD9gBNexd+9eoqOja63iUavVLFy4kHvvvZfg4OBr7kAPHDjAkCFD0Gq1/PTTT2KNQXAIhyV1mdVqxcPDA5PJRFpaGidPniQnJ4fz588DoNfr+e2332p9D5VKRa9evQgICLjuc+RReMeOHdFoNNx8880A+Pr60rlzZzw8PGqsAPHw8LBtEReJWIDLP5MGgwGj0YhGo7EtAl85Iv8zk8nEkCFDyM7O5tNPP2Xq1KkOjlpwVw5P6oLgDiZOnMiWLVuIiIhgz549LreOJLgukdQFoZllZGQwcOBA1Go1P/30k+hjJDhUk08+MplMta76C4K7Wbt2LQAvv/yySOiCwzVopF5eXs6XX37Jl19+SVlZma3kLiAggDfeeINJkyaJ20zBreXn56PVavHy8uLUqVOihl9wuHqP1NPT0xkwYACzZ8+mrKyM06dPU1RUhEqloqioiClTpjBhwoSrNtIIgruJiYkBYP78+SKhC4qoV1LPzc0lPDycdu3aceTIEY4fP44kSWzdupULFy6QmZmJVqslLi6OgIAAEhIS7B23IDgdg8HAsmXLAHj00UcVjkZwV3UmdZPJxOTJkwFISEjgjjvuAOD06dOMHz8eDw8PgoODWb58OXB5V2VmZqYdQxYE57Rt2zYkSWLWrFmifbSgmFp7v1itViZPnkxGRgaJiYn06NHD9tifa7jlufTp06fz3HPP2SFUQXBekiTZFkinTZumcDSCO6t1pH7o0CF2797NmjVriIiIqPWN5Ln0gQMH1trSVRBaogMHDpCXl0d4eDihoaFXPWaxWGx9gwTB3modqX/++ed4eXkxZcqUer9h+/btmxyUILgKuVvll19+CVzuyLh8+XKqqqr44YcfqKiooKCggCeffJI33nhD4WgFd1BrUj948CBDhgxp0MhbJHWhJTOZTCxatIiDBw9y8eLFa9odr1u37prXaLVaHn74YUeFKLi5OvupNzRJnzt3rtHBCIKzq6ysJD4+Hh8fH1q3bs2oUaNo3749W7ZsAWD16tXcfvvteHl54efnJzYfCQ5Xa1L39/cnMzPT1oSrPupqxiUIriwwMJCzZ89e83U5qUdGRopELiiq1oXSiRMnkp2dTVxcXJ1vJHdZ7NatW/NEJgiCIDRYrW0CLBYLY8aMIT09nbS0NIKDg2t8XlVVFf3798dgMHD69GnRslZwK1arlVatLt/0XrhwQZxuJCiq1pG6p6cna9euRaVSMXToULKysq55jtVq5fHHHycvL48VK1aIhC64nT8fiCIISqpzR2mPHj1ISUkBYOjQoVcdtQaXV/u3bNnCnDlzmDFjhn2iFAQnZrFYgMtHFgqC0urV+yU4OJh9+/bh5+fH0KFDeeONN7BYLMTHxzNnzhzCwsJYvny56NAouLWazqAVBEdrUOvdqv/f3v2CNBPHcRx/gzDLWSaChzCLluFwoEWMrhhMBkVZEUyCiDiFdcOa0RkMhlkuTG2HgwUPYcE/KFcUVgwrHvgnCYMnuccH8dmdzk3c5xXHN3zTB/a77+/3fX5mbW2NbDZb2zM6ODjI8fExkUjkO/sU+dE6OzuJRqOcn5+3uhVpc3Xn1N8yDIPt7W0eHx9rI1zDw8NaqCtt7eHhgZeXl9pjdyKtFHjzkW3b7O/vE4/HyWQyHB4eMjQ0RC6X0wYkaUuGYWCaJpOTk61uRSTY8UuhUCCRSGCaJpeXl/T09OC6LktLSxSLReLxOAcHBzqKkbZTqVQIh8P61yot5zvUr66uGB8fxzAMzs7O/rk1V61WsSyLxcVFent7dcYuItIivo9fdnZ2AGpTMG91dHQwMzOD4zh4nkcikcDzvMZ2KiIidfkK9Wq1ysnJCSMjI0Sj0Q/rYrEYR0dH3NzckE6nG9akiIj44yvUXdfl4uKC2dnZurVjY2Nsbm6SzWbfXVQSEZHv5SvUX6/+7+7u+trgsry8jGmatfVeIiLSHL5CPRKJsLW1RalUolQq1a03DIOVlRUsy6JcLn+5SRER8cf3h9JkMkl3dzepVMpX/cTEBADX19ef60xERALzHerhcJj19XUcx8F13br1r+/AaBOSiEjzBLpROj8/TygUIpPJ1K29v78H0BYYEZEmChTqfX19bGxssLe3h23bH9Z5nkc6naarq4vR0dEvNykiIv4EeiYA/m45Asjn8+/m1svlMslkEsdxsCyL6enpxnUrIiL/FTjUAU5PT5mamuLp6YnV1VVisRh3d3cUCgVs2yYUCpHL5RToIiJN9qlQB7i9vSWVSpHP52u/9ff3s7CwwNzcHAMDAw1rUkRE/Pl0qL/yPI9KpYJhGHrES0Skxb4c6iIi8nMEXpIhIiI/l0JdROQXUaiLiPwifwDvfoUBRHaOBAAAAABJRU5ErkJggg=="
    }
   },
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Here is a *beautiful* hand-drawn picture of a cube:\n",
    "![image.png](attachment:image.png)\n",
    "* Find a list of rotations which generate all symmetries of this cube in $\\mathrm{SO}(3)$.\n",
    "* Compute the subgroup $H$ of $S_8$ generated by the permutations these rotations induce on the corners of the cube.\n",
    "* Find out what group it is and verify your answer with the ``is_isomorphic`` function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "* The rotations $a_x, a_y, a_z$ around the three coordinate axes generate the group of all rotations (hint to prove this: the group generated by these three rotations acts transitively on the $6$ faces of the cube, and the stabilizer of the top face in the group of *all* rotations is generated by $a_z$). The action on the vertices is as follows:\n",
    "```\n",
    "ax = ((2,6,7,3),(1,5,8,4))\n",
    "ay = ((3,4,8,7),(2,1,5,6))\n",
    "az = ((1,2,3,4),(5,6,7,8))\n",
    "```\n",
    "* The group $H$ generated by these is:\n",
    "```\n",
    "H = PermutationGroup([az, ax, ay])\n",
    "```\n",
    "* The most basic invariant of a group is its order:\n",
    "```\n",
    "H.order()\n",
    "> 24\n",
    "```\n",
    "Well, we know a very nice group of order $24$, namely the symmetric group $S_4$. Let's check whether $H$ is isomorphic to $S_4$:\n",
    "```\n",
    "H.is_isomorphic(SymmetricGroup(4))\n",
    "> True\n",
    "```\n",
    "For more information see e.g. [here](https://en.wikipedia.org/wiki/Octahedral_symmetry).\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course SageMath also knows about subgroups, their properties (like being **normal**) and quotient groups."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = SymmetricGroup(3)\n",
    "a = G('(1,2,3)')\n",
    "H = G.subgroup([a]); H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H.is_normal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.quotient(H)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also list all subgroups of $G$ (possibly up to conjugation):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(G.subgroups())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(G.conjugacy_classes_subgroups())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "An element $\\sigma \\in S_n$ is called a *derangement* if the permutation $\\sigma$ of $\\{1, \\ldots, n\\}$ has no fixed point, i.e. if $\\sigma(i) \\neq i$ for all $1 \\leq i \\leq n$.\n",
    "Denote by $D_n$ the number of derangements in $S_n$, so that $p_n = D_n/n!$ is the probability that a random permutation $\\sigma \\in S_n$ has no fixed points. Make some experiments and guess a formula for the limit of $p_n$ as $n \\to \\infty$.<br>\n",
    "*Hint:* Maybe look at some examples of $1/p_n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Suggested sub-exercises* (uncomment to see)\n",
    "<!---\n",
    "* Write a function ``is_derangement(sigma, n)`` checking whether a permutation ``sigma`` in the symmetric group on ``n`` letters is a derangement. *Hint* The Python function ``all`` can be useful here.\n",
    "* Write a function ``p(n)`` computing the number $p_n$.\n",
    "* Print numerical values for $1/p_n$ in several examples, and try to guess what this converges to. *Hint:* If you have accidentally overwritten the function ``n``, you can use e.g. ``r.n()`` to get an approximation of a rational number ``r``, or use ``restore('n')`` to get the function ``n`` back.\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "While it is possible to solve this exercise using one big block of code, it is much nicer to write several functions in preparation and then have a very short block of code doing the actual work.\n",
    "\n",
    "So first, we write a function which checks whether a permutation ``sigma`` in $S_n$ is a derangement. For convenience, we hand over the parameter ``n`` as well, though this could be reconstructed from ``sigma`` in principle.\n",
    "```\n",
    "def is_derangement(sigma, n):\n",
    "    return all(sigma(i) != i for i in range(1,n+1))\n",
    "```\n",
    "Here we used the ``all`` construction, which takes an iterable spitting out bools and returns ``True`` if and only if all those bools were ``True``.\n",
    "\n",
    "Next, we want a function computing the numbers $p_n$. The following is the most straightforward way to do it:\n",
    "```\n",
    "def p(n):\n",
    "    count = 0\n",
    "    for sigma in SymmetricGroup(n):\n",
    "        if is_derangement(sigma, n):\n",
    "            count += 1\n",
    "    return count / factorial(n)\n",
    "```\n",
    "However, using a clever combination of ``sum`` and a list comprehension, we can make this much shorter:\n",
    "```\n",
    "def p(n):\n",
    "    return sum(1 for sigma in SymmetricGroup(n) if is_derangement(sigma,n))/factorial(n)\n",
    "```\n",
    "With either of the functions, we can now look at some values of $1/p_n$, as suggested in the hint. Here we might run into a weird problem: given a fraction as in the output of ``p`` we would normally write ``n(p/q)`` to get its decimal representation. But probably the variable ``n`` is already used in the ``for``-loop and thus *overwrites* the standard function ``n``. We can solve this by using the *method* ``n`` of Rationals in SageMath: \n",
    "```\n",
    "for n in range(2,12):\n",
    "    print(1/p(n).n())\n",
    "> \n",
    "2.00000000000000\n",
    "3.00000000000000\n",
    "2.66666666666667\n",
    "2.72727272727273\n",
    "2.71698113207547\n",
    "2.71844660194175\n",
    "2.71826333176026\n",
    "2.71828369389345\n",
    "2.71828165766640\n",
    "2.71828184277783\n",
    "```\n",
    "Staring at these numbers a bit, we can guess that they converge to the Euler constant $e$:\n",
    "```\n",
    "e.n()\n",
    "> 2.71828182845905\n",
    "```\n",
    "And indeed it is true that $1/p_n \\to e$ and thus $p_n \\to 1/e$ for $n \\to \\infty$, see [this wikipedia page](https://en.wikipedia.org/wiki/Derangement#Growth_of_number_of_derangements_as_n_approaches_%E2%88%9E).\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also do some computations with group homomorphisms (though I would say this is less well-developed). To specify such a homomorphism from $G$ to $H$ , we need to specify the images of the generators of $G$. Let's try to construct a homomorphisms from $G = S_5$ to the cyclic group $H$ of order $4$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = SymmetricGroup(5)\n",
    "G.gens()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = CyclicPermutationGroup(4)\n",
    "list(H)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I claim that there exists a homomorphism $\\varphi : G \\to H$ sending $(1,2,3,4,5)$ to the neutral element, and sending $(1,2)$ to the element $(1,3)(2,4)$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "phi = PermutationGroupMorphism_im_gens(G, H, [H('()'), H('(1,3)(2,4)')]); phi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can compute image and kernel of this morphism and verify the **first isomorphism theorem**:\n",
    "> Given a group homomorphism $\\varphi : G \\to H$ we have $\\mathrm{im}(\\varphi) \\cong G/\\mathrm{ker}(\\varphi)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "im = phi.image(G); im"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ker = phi.kernel(); ker"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "im.is_isomorphic(G.quotient(ker))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are many more properties of groups and their elements which can be checked or computed using SageMath (e.g. whether a group is **abelian** or **simple**, the **order** of an element, etc). For most of these, you should be able to find them simply by guessing the name and using ``Tab``-completion, or by googling)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, there are also [libraries](https://gap-packages.github.io/smallgrp/doc/chap1.html#X7C16EA1580AC7586) containing all isomorphism classes of groups of a given (small) order, in particular those of order at most 1023. This can be useful e.g. for checking a conjecture that you might have, or for trying to identify a given group. These libraries are implemented in the computer algebra system [GAP](https://www.gap-system.org/), which SageMath uses in the background to do group theory computations. \n",
    "\n",
    "When preparing this lecture, I found that there was not really a convenient way to access these databases, but based on [this answer on math.stackexchange](https://math.stackexchange.com/questions/185534/converting-gap-groups-into-sage-permutation-groups) it is not so hard to write a function for this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gap_group_to_SageMath(A):\n",
    "    B = A.IsomorphismPermGroup()\n",
    "    return PermutationGroup(gap_group = B.Image())\n",
    "\n",
    "def groups_of_order(n):\n",
    "    number = ZZ(gap.NumberSmallGroups(n))\n",
    "    # groups numbered from 1 to number\n",
    "    return [gap_group_to_SageMath(gap.SmallGroup(n,i)) for i in range(1,number+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "groups_of_order(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "groups_of_order(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "groups_of_order(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "The [Feit-Thompson theorem](https://en.wikipedia.org/wiki/Feit%E2%80%93Thompson_theorem) states that every group of odd order is *solvable*. Check the theorem for orders at most 99.<br>\n",
    "*Remark:* A group $G$ is *solvable* if there exists a sequence of subgroups\n",
    "$$\n",
    "1 = G_0 < G_1 < \\ldots < G_k = G\n",
    "$$\n",
    "such that $G_{j-1}$ is normal in $G_j$ and such that the quotient $G_j / G_{j-1}$ is abelian for $j=1, \\ldots, k$. However, you won't need to know this for solving the exercise ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "Using ``groups_of_order`` from above, we can go through the groups of any given order. We only have to guess (or google) that ``G.is_solvable()`` decides whether a group is solvable.\n",
    "```\n",
    "for n in range(1,100,2):\n",
    "    check = all(G.is_solvable() for G in groups_of_order(n))\n",
    "    print(n, check)\n",
    "> \n",
    "1 True\n",
    "3 True\n",
    "5 True\n",
    "...\n",
    "99 True\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just for fun, we finish with a nice picture: given a group $G$ with generating set $S$, the **Cayley graph** of $(G,S)$ is the oriented graph which has one vertex for each element of the group, and an oriented edge from $g$ to $gh$ for each $g \\in G,h \\in S$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = DihedralGroup(6)\n",
    "H.cayley_graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a fun application of group theory: [this lecture](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec38.html) explains how to solve a Rubik's cube using SageMath (in fact, the interface of SageMath to GAP)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Polynomial rings and field extensions\n",
    "Given a base ring $R$, we can create the polynomial ring $S = R[x_1, ..., x_n]$ over $R$, where we can choose the variable names freely. Here is an example with the base ring $R = \\mathbb{Q}$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S.<x,y> = PolynomialRing(QQ)\n",
    "f = x^2 + 2*x*y + y^2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compared to symbolic expressions in the variables ``x,y``, the polynomials in ``S`` have some additional functions (which don't make sense for general symbolic expressions):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f.degree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that an element $f$ of a ring $S$ is *prime* if $p \\neq 0$ and $p$ is not a unit and whenever $p$ divides $a \\cdot b$ for some $a,b \\in S$ then $p$ divides $a$ or $p$ divides $b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f.is_prime()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $S = \\mathbb{Q}[x,y]$ is a *unique factorization domain*, an element which is not prime must be *reducible*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "factor(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The construction ``S.<x,y,...> = PolynomialRing(QQ)`` automatically sets the variables ``x,y,...`` to be generators of the new ring ``S``. We can also first create the ring abstractly, and then get our hands on the generators manually:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = PolynomialRing(ZZ, 'x', 9); T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = T.gens(); X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = X[0]*X[1]; g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Is the polynomial $f=X^8 + Y^8$ a prime element in \n",
    "* $\\mathbb{Q}[x,y]$\n",
    "* $\\mathbb{F}_2[x,y]$\n",
    "\n",
    "If not, specify a factorization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "S.<x,y> = PolynomialRing(QQ)\n",
    "f = x^8 + y^8\n",
    "f.is_prime()\n",
    "> True\n",
    "S.<x,y> = PolynomialRing(GF(2))\n",
    "f = x^8 + y^8\n",
    "f.is_prime()\n",
    "> False\n",
    "factor(f)\n",
    "> (x + y)^8\n",
    "```\n",
    "This last factorization is an example of the [freshman's dream](https://en.wikipedia.org/wiki/Freshman%27s_dream) coming true: in characteristic $p$ it is true that $(x+y)^q = x^q + y^q$ for $q=p^r$ a power of $p$.\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a polynomial, we can get access to its coefficients as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S.<x,y> = PolynomialRing(QQ)\n",
    "f = x^2 + 2*x*y + y^2 + 17*x + 32\n",
    "f.dict()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using polynomials, we can now also play around with finite *field extensions*. Recall that given a field $K$ and an irreducible polynomial $g \\in K[x]$, the quotient $S = K[x]/(g)$ is a field extension of $K$ of order $\\mathrm{deg}(g)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P.<x> = PolynomialRing(QQ)\n",
    "g = x^2 + 1\n",
    "g.is_irreducible()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S.<i> = QQ.extension(g)\n",
    "S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S.degree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since in the ring $S$ we adjoined a root of the polynomial $g$, it is no longer irreducible considered as an element of $S[x]$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q.<x> = PolynomialRing(S) # the ring Q = S[x]\n",
    "gS = Q(g)                 # gS is the polynomial g = x^2 + 1 seen as an element of Q\n",
    "gS.is_irreducible()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "factor(gS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Construct the following field extensions of $K = \\mathbb{Q}$:\n",
    "$$\n",
    "L = K[x]/(x^2-2),\\\\\n",
    "N = L[y]/(y^2-x).\n",
    "$$\n",
    "Check that $L/K$ and $N/L$ are *Galois* extensions (use ``Tab``-completion and the documentation via ``?`` to find the right commands). Also check that $N/K$ is *not* Galois. This is the classical example showing that it's not true that the composition of two Galois extensions is Galois.<br>\n",
    "*Bonus exercise:* Find an irreducible polynomial $g \\in \\mathbb{Q}[x]$ which has a root in $N$ but does not split as a product of linear factors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "K = QQ\n",
    "S.<x> = PolynomialRing(K)\n",
    "L.<a> = K.extension(x^2-2)\n",
    "L.is_galois() # L/K is Galois\n",
    "> True\n",
    "T.<y> = PolynomialRing(L)\n",
    "N.<b> = L.extension(y^2-a)\n",
    "N.is_galois_relative() # N/L is Galois\n",
    "> True\n",
    "N.is_galois_absolute() # N/K is not Galois\n",
    "> False\n",
    "```\n",
    "Why is this extension not Galois? If you [recall](https://en.wikipedia.org/wiki/Galois_extension), one of the equivalent conditions of $N/K$ being Galois would be that every irreducible polynomial in $K[x]$ with at least one root in $N$ splits over $N$ and is separable. However, the polynomial $g = x^4 - 2 \\in \\mathbb{Q}[x]$ does not satisfy this:\n",
    "```\n",
    "g = x^4-2\n",
    "g.is_irreducible()\n",
    "> True\n",
    "U.<x> = PolynomialRing(N)\n",
    "gU = U(g)\n",
    "factor(gU)\n",
    "> (x - b) * (x + b) * (x^2 + a)\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Speaking of Galois extensions: we can of course also compute the Galois group of a field extension, and it naturally operates on elements of the larger field:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "P.<x> = PolynomialRing(QQ)\n",
    "g = x^2 + 1\n",
    "S.<i> = QQ.extension(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = S.galois_group(); G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G[1](i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we can create ideals in polynomial rings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "PR.<x,y> = PolynomialRing(QQ)\n",
    "f = x^2 - y\n",
    "g = x^3 - x\n",
    "J = Ideal([f,g])\n",
    "J"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y-x^4 in J"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "J.is_prime()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(y in J, y-1 in J)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y*(y-1) in J"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the background, SageMath computes a so-called [*Gröbner basis*](https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis) of the ideal $J$. This is a particular set of generators of the ideal, such that there exist algorithms for answering questions like:\n",
    "* is a given element of the polynomial ring contained in the ideal,\n",
    "* are two ideals $J_1, J_2$ equal,\n",
    "* what is the intersection $J_1 \\cap J_2$ of two ideals, ...\n",
    "\n",
    "In some cases, these can even be used to compute the solution set of a system of polynomial equations explicitly, in particular if this solution set is finite. Here is how we compute the solution set of the equations\n",
    "$$ x^2 -y = 0, x^3 - x = 0 $$\n",
    "above, whose left-hand sides generate the ideal $J$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = J.variety(QQ); X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are really interesting topics and algorithms, but since this lecture focuses primarily on applications, we will not go further into details here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assignments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Compute the following:\n",
    "* the list of prime numbers between 100 and 200 which end in the digit '3'\n",
    "* the number of matrices in $\\mathrm{Mat}_{4 \\times 4}(\\mathbb{F}_2)$ which are invertible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)\n",
    "<!---\n",
    "```\n",
    "[p for p in range(100,201) if ZZ(p).is_prime() and p % 10 == 3]\n",
    "> [103, 113, 163, 173, 193]\n",
    "```\n",
    "Since ``matrix(GF(2),n,m,L)`` for a list ``L`` of $n \\cdot m$ integers will simply fill the $n \\times m$-matrix with these integers row by row, the following works:\n",
    "```\n",
    "from itertools import product\n",
    "# create all matrices\n",
    "M = [matrix(GF(2),4,4,L) for L in product(GF(2), repeat=16)]\n",
    "# select the ones that are invertible\n",
    "N = [m for m in M if m.is_invertible()]\n",
    "len(N)\n",
    "> 20160\n",
    "```\n",
    "The following is much shorter, but uses the function ``MatrixSpace`` to create the list ``M`` above:\n",
    "```\n",
    "len([A for A in MatrixSpace(GF(2),4) if A.is_invertible()])\n",
    "> 20160\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "For a subgroup $G \\subseteq S_n$ of $S_n$, denote by\n",
    "$$\n",
    "p(G) = \\frac{|\\{\\sigma \\in G: \\sigma\\text{ is a derangement}\\}|}{|G|}\\,.\n",
    "$$\n",
    "The numbers $p_n$ from the first exercise about derangements above are exactly $p_n = p(S_n)$. Last year, my friend Kaloyan Slavov (working at ETH Zurich) and Bjorn Poonen showed the following fun theorem.<br>\n",
    "> **Theorem** ([PS21](https://arxiv.org/abs/2107.02724))<br>\n",
    "> If a subgroup $G \\subseteq S_n$ satisfies $p(G) = p_n$, then $G = S_n$.\n",
    "\n",
    "Using clever arguments, they prove the theorem for $n \\geq 12$, and for $n \\leq 11$ they use a computer program written in [Magma](https://en.wikipedia.org/wiki/Magma_(computer_algebra_system)). However, Magma is neither free nor open source! Show them that SageMath can also be used to prove their theorem for $n \\leq 11$!<br>\n",
    "*Hint:* We already had an exercise about derangements above, so you might be able to recycle some of your code there!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "We take code from the previous exercise, but modify the function ``p`` to now take a permutation group ``G`` and return the number $p(G)$:\n",
    "```\n",
    "def is_derangement(sigma, n):\n",
    "    return all(sigma(i) != i for i in range(1,n+1))\n",
    "\n",
    "def p(G,n):\n",
    "    return sum(1 for sigma in G if is_derangement(sigma,n))/G.order()\n",
    "```\n",
    "Now we write a function ``check`` verifying the theorem for a given $n$. Note that we don't have to go through *all* subgroups of $S_n$, it suffices to go through any *conjugacy class* of a subgroup. The reason is that a permutation is a derangement iff any conjugate of the permutation is a derangement.\n",
    "```\n",
    "def check(n):\n",
    "    H = SymmetricGroup(n)\n",
    "    pn = p(H,n)\n",
    "    for G in H.conjugacy_classes_subgroups():\n",
    "        # if G is a proper subgroup but has same p(G) as p(S_n), then we found a counter-example\n",
    "        if G.order()<factorial(n) and p(G,n)==pn:\n",
    "            return (False, G)\n",
    "    # if we didn't find a counter-example, then the theorem is true\n",
    "    return True\n",
    "```\n",
    "Now we can run it for $n=2, \\ldots, 11$, which can take a while:\n",
    "```\n",
    "for n in range(2,6):\n",
    "    print(n, check(n))\n",
    "> \n",
    "2 True\n",
    "3 True\n",
    "...\n",
    "11 True\n",
    "```\n",
    "--->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Compute the splitting field $T$ of the polynomial $g = x^5 - 3 x^3 + x^2 -3 \\in \\mathbb{Q}[x]$ by iteratively adjoining roots of the polynomial to $\\mathbb{Q}$. What is the degree of the field extension $T/\\mathbb{Q}$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution** (uncomment to see)<br>\n",
    "<!---\n",
    "If we start naively, we get an error message:\n",
    "```\n",
    "R.<x> = PolynomialRing(QQ)\n",
    "g = x^5-3*x^3+x^2-3\n",
    "S.<a> = QQ.extension(g)\n",
    "> \n",
    "---------------------------------------------------------------------------\n",
    "ValueError\n",
    "...\n",
    "ValueError: defining polynomial (x^5 - 3*x^3 + x^2 - 3) must be irreducible\n",
    "```\n",
    "So in fact the polynomial $g$ is not irreducible! Ok, let's factor it:\n",
    "```\n",
    "factor(g)\n",
    "> (x + 1) * (x^2 - x + 1) * (x^2 - 3)\n",
    "```\n",
    "The root $x=-1$ is already contained in $\\mathbb{Q}$, so let's first adjoin the root of $x^2-3$ and then the one of $x^2-x+1$. Note that below we don't have to introduce a new polynomial ring in each step, since SageMath is smart enough to recognize what we are trying to do:\n",
    "```\n",
    "S.<a> = QQ.extension(x^2-3); S\n",
    "> Number Field in a with defining polynomial x^2 - 3\n",
    "T.<b> = S.extension(x^2-x+1); T\n",
    "> Number Field in b with defining polynomial x^2 - x + 1 over its base field\n",
    "```\n",
    "Let's check that $g$ factors over $T$:\n",
    "```\n",
    "W.<x> = PolynomialRing(T)\n",
    "gT = W(g)\n",
    "factor(gT)\n",
    "> (x + 1) * (x - b) * (x - a) * (x + a) * (x + b - 1)\n",
    "```\n",
    "Computing the degree of the extension $T/\\mathbb{Q}$ then works as follows:\n",
    "```\n",
    "T.absolute_degree()\n",
    "> 4\n",
    "```\n",
    "See also Exercise 1 and solution on [this exercise sheet](https://www2.math.ethz.ch/education/bachelor/lectures/fs2014/math/algebra2/sol11) from which I took the polynomial above.\n",
    "--->"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}